Spanning Trees Review

Front

What is a spanning tree?

Back

A spanning tree of a graph is a subgraph that includes all the vertices of the graph and is a single connected tree, meaning it has no cycles.

Front

How do you calculate the number of spanning trees in a graph?

Back

The number of spanning trees can be calculated using various methods, including Kirchhoff's matrix tree theorem, which involves the determinant of a modified Laplacian matrix of the graph.

Front

What is Kruskal's algorithm used for?

Back

Kruskal's algorithm is used to find the minimum spanning tree of a connected, weighted graph by adding edges in order of increasing weight, ensuring no cycles are formed.

Front

What is the difference between a spanning tree and a minimum spanning tree?

Back

A spanning tree includes all vertices with the minimum number of edges, while a minimum spanning tree is a spanning tree with the least total edge weight.

Front

What is a cycle in a graph?

Back

A cycle is a path in a graph that starts and ends at the same vertex, with all edges and vertices distinct except for the starting and ending vertex.

Front

What does it mean for a graph to be connected?

Back

A graph is connected if there is a path between every pair of vertices, meaning all vertices are reachable from one another.

Front

What is the significance of the number of spanning trees in a network?

Back

The number of spanning trees indicates the different ways to connect all vertices without cycles, which is important for network design and reliability.

Front

How can you determine if a graph has a unique spanning tree?

Back

A graph has a unique spanning tree if all edges have different weights, ensuring that there is only one way to connect all vertices with the minimum total weight.

Front

What is the role of edge weights in spanning trees?

Back

Edge weights determine the cost of including an edge in a spanning tree; in minimum spanning trees, edges with lower weights are preferred.

Front

What is a complete graph?

Back

A complete graph is a graph in which every pair of distinct vertices is connected by a unique edge.