A spanning tree is a connected acyclic subgraph containing every vertex. A minimum spanning tree minimizes the sum of edge weights over all spanning trees. In a three-vertex triangle with every edge weight 1, deleting any of the three edges gives a different spanning tree of total weight 2. Hence there are three minimum spanning trees; minimum total weight need not mean a unique tree.
True. Every spanning tree contains precisely the vertex set by definition. Thus every minimum spanning tree has nodes, independently of the weights or which minimum tree is chosen.
True. Every finite tree on vertices has exactly edges. One proof removes a leaf and its incident edge, preserving a tree on one fewer vertex, and applies induction from the one-vertex tree. Therefore all minimum spanning trees have the same edge count.
False. Take a triangle with and . Its unique minimum spanning tree uses and , with total weight 4. The shortest path from to in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.
Prim's algorithm grows a tree from any root . For each vertex outside the current tree, its priority queue key is the cheapest single edge connecting it to the tree, not the total length of a root-to-vertex path:The indexed priority queue supports membership and locating a vertex's heap entry. After the first extraction, the chosen parent edge is a least-weight edge crossing the cut between the current tree and its complement. The minimum spanning tree cut property makes that edge safe: exchanging it for a crossing edge of a suitable minimum tree preserves minimality. Repeating this establishes a minimum tree. Connectivity ensures every nonroot vertex eventually has a parent; edge weights may be negative.
for v in V:
key[v] = infinity
parent[v] = NONE
key[r] = 0
Q = indexed_min_priority_queue(V, key)
while Q is not empty:
u = Q.extract_min()
for (v,weight) in adjacency[u]:
if Q.contains(v) and weight < key[v]:
parent[v] = u
key[v] = weight
Q.decrease_key(v, weight)
return {(parent[v],v) : v != r}An indexed binary heap builds the initial queue in time;
extract_min and decrease_key each cost , while a position table supports membership in . There are extractions and at most edge inspections, with at most one successful decrease per inspection. Thus the bound is , or for a connected graph with at least two vertices. The singleton case is constant time. An unindexed heap cannot provide decrease-key by vertex without an additional position structure. Articles by others on the same topic
There are currently no matching articles.