CODEWITHSUNDEEP
algorithmgraph-algorithmminimum-spanning-treeprims-algorithmspanning-tree
julieb
julieb

Reputation: 43

How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?

I'm learning the requirements for finding a minimum spanning tree for a connected, undirected graph with distinct edge costs. One of the requirements is that there must be no cycles created in the tree, and the reason given for why a cycle isn't created by, for example Prim's algorithm, is that "an edge which is the only edge crossing a cut cannot create a cycle" (Lonely cut corollary). However, when I look at a cut, I normally see multiple edges crossing the cut. They do not necessarily connect the same two vertices, but there are multiple edges nevertheless. Shouldn't the lonely cut corollary be worded as "an edge which is the only one crossing a cut and connecting two specific vertices in each set"? Or am I just misunderstanding the corollary?

Upvotes: 0

Views: 182

Answers (2)

julieb
julieb

Reputation: 43

After going back and reviewing the material again, I realized I was conflating edges of the original graph with edges of the graph being selected to create the tree by Prim's algorithm. As long as an edge crossing a cut is the first one added by the algorithm to cross that particular cut, no cycles are being created and Prim outputs a tree.

Upvotes: 0

Kelly Bundy
Kelly Bundy

Reputation: 27629

How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?

It isn't.

And thus the corollary doesn't say anything about it. It only says something about an edge IF you have a lonely cut.

Upvotes: 0

Related Questions