UFCxKING121
New member
- Joined
- Apr 5, 2015
- Messages
- 2
So this is the whole question.
Use Kruskal's algorithm to show that if G is a connected graph, then any (not necessarily connected) sub graph that contains no circuits is part of some spanning tree for G. Consider both the weighted and unweighted cases.
I know how to use Kruskal's algorithm to find minimum spanning trees, but this question is really throwing me off. I kind of understand what it is saying, and can visualize it, but I cannot really come to any conclusions on actually solving it. If G is a connected sub graph, and you use Kruskal's algorithm to solve for the minimum spanning tree, I see that you can get multiple sub graphs, but I do not see how that is answering the question. I am honestly very lost and confused on what to do.
Use Kruskal's algorithm to show that if G is a connected graph, then any (not necessarily connected) sub graph that contains no circuits is part of some spanning tree for G. Consider both the weighted and unweighted cases.
I know how to use Kruskal's algorithm to find minimum spanning trees, but this question is really throwing me off. I kind of understand what it is saying, and can visualize it, but I cannot really come to any conclusions on actually solving it. If G is a connected sub graph, and you use Kruskal's algorithm to solve for the minimum spanning tree, I see that you can get multiple sub graphs, but I do not see how that is answering the question. I am honestly very lost and confused on what to do.