Discrete Structure05 marksSpanning trees
Define spanning tree. Explain minimum spanning tree with example.
Define spanning tree. Explain minimum spanning tree with example. [5]
A spanning tree of a connected, undirected graph G = (V, E) is a subgraph that: - Includes all vertices of the graph - Is a tree (connected and acyclic) - Has exactly V - 1 edges A graph with n vertices will have a spanning tree with exactly n - 1 edges. --- A Minimum Spanning Tree is a spanning ...