Definition

Let G be a connected graph, then the sub-graph H of G is called a spanning tree of G if −

• H is a tree
• H contains all vertices of G. A spanning tree T of an undirected graph G is a subgraph that includes all of the vertices of G.

Key Points About Spanning Trees:

• Includes All Vertices: A spanning tree must include all vertices from the original graph.
• Minimum Edges: For a graph with \(n\) vertices, a spanning tree has exactly \(n-1\) edges.
• No Cycles: Spanning trees do not contain any cycles, ensuring the structure remains a tree.
• Connectivity: Despite having the minimum number of edges, a spanning tree maintains the graph’s connectivity.

Examples:

Consider a simple graph:

A - B - C
|   |
D - E

Possible spanning trees of this graph include: 1.

A - B - C
|   
D - E

A - B
|   
D - E - C

Applications:

• Network Design: Ensuring all nodes in a network are connected with the minimum number of connections.
• Optimization: Used in algorithms to minimize the cost of connecting points.
• Cluster Analysis: In data clustering algorithms to find minimal connecting clusters.

Algorithms to Find Spanning Trees:

• Kruskal’s Algorithm: Finds the minimum spanning tree by adding the smallest edges while avoiding cycles.
• Prim’s Algorithm: Builds the minimum spanning tree by starting from an arbitrary vertex and adding the smallest edge that expands the tree.

Spanning trees play a crucial role in network design, optimization problems, and various applications in computer science and mathematics.

Theorem Statement:

Let \(G\) be a connected graph with \(n\) vertices. Construct the Laplacian matrix \(L\) of \(G\), which is defined as: \[ L = D - A \] where: - \(D\) is the degree matrix: a diagonal matrix where the \(i\)-th diagonal element is the degree of the \(i\)-th vertex. - \(A\) is the adjacency matrix: a matrix where the element \(A_{ij}\) is 1 if there is an edge between vertex \(i\) and vertex \(j\), and 0 otherwise.

Kirchhoff’s Theorem:

The number of spanning trees \(\tau(G)\) of a graph \(G\) is equal to any cofactor of the Laplacian matrix \(L\). More formally: \[ \tau(G) = \det(L_{ij}) \] where \(L_{ij}\) is the matrix obtained by deleting the \(i\)-th row and \(j\)-th column from \(L\).

Example:

Consider a simple graph \(G\) with vertices \(A, B, C\) and edges \(\{(A,B), (A,C), (B,C)\}\).

1. Degree Matrix \(D\): \[ D = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{pmatrix} \]

2. Adjacency Matrix \(A\): \[ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{pmatrix} \]

3. Laplacian Matrix \(L\): \[ L = D - A = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \\ \end{pmatrix} \]

4. Deleting the First Row and Column of \(L\): \[ L_{11} = \begin{pmatrix} 2 & -1 \\ -1 & 2 \\ \end{pmatrix} \]

5. Determinant of \(L_{11}\): \[ \det(L_{11}) = (2 \times 2) - (-1 \times -1) = 4 - 1 = 3 \]

Thus, the number of spanning trees \(\tau(G)\) in the given graph \(G\) is 3.

Example

Kirchhoff’s Theorem is a powerful tool in combinatorial mathematics and has applications in network reliability, electrical engineering, and more. Let me know if you need further clarification or examples!Kirchhoff’s Theorem, also known as the Matrix-Tree Theorem, is a fundamental result in graph theory. It relates the number of spanning trees of a connected graph to the determinant of a specific matrix derived from the graph. This theorem is named after Gustav Kirchhoff, a physicist who made significant contributions to the understanding of electrical circuits and graph theory.

Theorem Statement:

Let \(G\) be a connected graph with \(n\) vertices. Construct the Laplacian matrix \(L\) of \(G\), which is defined as: \[ L = D - A \] where: - \(D\) is the degree matrix: a diagonal matrix where the \(i\)-th diagonal element is the degree of the \(i\)-th vertex. - \(A\) is the adjacency matrix: a matrix where the element \(A_{ij}\) is 1 if there is an edge between vertex \(i\) and vertex \(j\), and 0 otherwise.

Kirchhoff’s Theorem:

The number of spanning trees \(\tau(G)\) of a graph \(G\) is equal to any cofactor of the Laplacian matrix \(L\). More formally: \[ \tau(G) = \det(L_{ij}) \] where \(L_{ij}\) is the matrix obtained by deleting the \(i\)-th row and \(j\)-th column from \(L\).

Example:

Consider a simple graph \(G\) with vertices \(A, B, C\) and edges \(\{(A,B), (A,C), (B,C)\}\).

1. Degree Matrix \(D\): \[ D = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{pmatrix} \]

2. Adjacency Matrix \(A\): \[ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{pmatrix} \]

3. Laplacian Matrix \(L\): \[ L = D - A = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \\ \end{pmatrix} \]

4. Deleting the First Row and Column of \(L\): \[ L_{11} = \begin{pmatrix} 2 & -1 \\ -1 & 2 \\ \end{pmatrix} \]

5. Determinant of \(L_{11}\): \[ \det(L_{11}) = (2 \times 2) - (-1 \times -1) = 4 - 1 = 3 \]

Thus, the number of spanning trees \(\tau(G)\) in the given graph \(G\) is 3.

Kirchhoff’s Theorem is a powerful tool in combinatorial mathematics and has applications in network reliability, electrical engineering, and more.

Example

Spanning Trees

A spanning tree \(T\) of a connected, undirected graph \(G\) is a tree composed of all the vertices and some (or perhaps all) of the edges of \(G\).

Informally, a spanning tree of \(G\) is a selection of edges of \(G\) that form a tree spanning every vertex. That is, every vertex lies in the tree, but no cycles (or loops) are formed. On the other hand, every bridge of \(G\) must belong to \(T\).

A spanning tree of a connected graph \(G\) can also be defined as a maximal set of edges of \(G\) that contains no cycle, or as a minimal set of edges that connect all vertices.

Subgraphs

We say that a graph H is a subgraph of a graph G if its vertices are a subset of the vertex set of G, its edges are a subset of the edge set of G, and each edge of H has the same end-vertices in G and H.

Definition

If H is a subgraph of G such that \(V(H) = V (G)\), then H is called a spanning subgraph of G. If H is a spanning subgraph which is also a tree, then H is said to be a spanning tree of G.

More tree terminology:

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.

Question 1

Let \(G\) be a graph. What two properties must \(G\) satisfy in order to be a tree?

Question 2

1. How many edges are in the spanning tree \(T\) ?

2. What is the sum of the degree sequence of \(T\)?

3. Write down all the possible degree sequences for the spanning tree \(T\).

(images/Graphs/edges_spinning_tree.jpg.png)

Question 3

Draw the tree \(T\) with \(V(T) = \{v_1,v_2,v_3,v_4,v_5,v_6\}\) and \(E(T)= \{v_1v_3, v_2v_3, v_3v_4,v_4v_5,v_4v_6\}\).

1. Construct all the non-isomorphic tree on seven vertices which may be obtained by adding a new vertex of degree one to \(T\).

2. Explain briefly why the trees you obtained are not isomorphic to each other.

Question 4

Let \(T\) be a rooted tree with root r.

1. Explain how the nodes of \(T\) are partitioned into levels.
2. What does it mean to say that \(T\) has height \(h\)?
3. What does it mean to say that a node of \(v\) is an external node?

Question 1

1. What properties must a graph satisfy in order for it to be a tree?

2. Design a balanced binary search tree for an ordered list of 15 records. Label the records \(1,2, \ldots , 15\) in your tree.

Question 2

A binary search tree is designed to store an ordered list of 50000 records, numbered \(1,2,3\ldots 50000\) at its internal nodes.

1. Draw levels 0, 1 and 2 of this tree, showing which number record is stored at the root and at each of the nodes at level 1 and 2, making it clear which records are at each level.

2. What is the maximum number of comparisons that would have to be made in order to locate an existing record from the list of 50000?

Question 3

Suppose a database, comprised of 30,000 internal nodes, is structured as a Binary Search Tree.

1. What is the key (number) of the Root node?

2. What are the keys of the nodes at level 1?

3. For the nodes at level1, how many subtrees are there?

4. State which nodes are in the substrees of the level 1 nodes?

5. How many nodes are the between the root (level 0) and level 7. (Hint: use a summation theorem)

6. What is the maximum number of searchs in this database?

Question 4

A binary search tree is designed to store an ordered list of 6000 records at its internal nodes.

1. Find which record is stored at the root (level 0) of the tree and at each of the nodes at level 1.

2. What is the height of the tree?