Skip to main content
added 165 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta et al, Papadimitrious and U. Vazirani.

formal definition of a minimum spanning tree

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.

Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes $$ \operatorname{weight}(T) = \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

graph example

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta et al.

formal definition of a minimum spanning tree

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

graph example

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.

Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes $$ \operatorname{weight}(T) = \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

graph example

Source Link
heretoinfinity
  • 649
  • 1
  • 6
  • 16

Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta et al.

formal definition of a minimum spanning tree

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

graph example