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?
How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?
139 Views Asked by julieb At
2
There are 2 best solutions below
0
julieb
On
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.
Related Questions in ALGORITHM
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in GRAPH-ALGORITHM
- Finding optimal swapping paths in employees moving to different cities
- How create an adjacency matrix of a Maze graph
- Convert python functions (shortestpath/ prediction function using nx.adamic_adar_index) into API
- How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?
- How to group nodes in a directed graph so that no two nodes in a group have paths between them?
- Is this total sink algorithm only for dags?
- What would be the best way to solve this maximum path graph problem, is Dijkstra possible even?
- Given undirected graph when removing edges one-by-one verify if removed one was a bridge and if so - the vertices of both parts
- Select n items from a set of subsets
- Implementing Kosaraju's Algorithm for SCC's
- modify current algorithm - APSP
- Does the removal of a few edges remove all paths to a node?
- Sliding Puzzle - DFS Issue
- Can we transform a graph in a way that applying DFS to the new graph would result in the same traversal order as applying BFS on the first graph?
- Advantages of linked lists in adjacency representation of a graph
Related Questions in MINIMUM-SPANNING-TREE
- Find a MST in O(V+E) Time in a Graph
- Boost minimum spanning tree with some edges included/excluded
- What is the correct vertex order of Prim algorithm from this graph?
- unique minimum spanning tree sufficient and necessary conditions
- Algorithm - minimum diameter spanning tree
- keep keys of different heaps updated when storing links to the same objects
- How to find maximum edge of path for all pairs of vertices of mst
- Adjacent spanning trees property
- Euclidean Minimal Spanning Tree and Delaunay Triangulation
- Minimum bottleneck spanning tree vs MST
- Running time of Kruskal's algorithm by varying the sorting time
- Minimum spanning tree of graph obtained by Prim's algorithm
- Proving optimality for a new algorithm that finds minimum spanning tree
- Prim's algorithm, using a priority queue
- Why Kruskal clustering generates suboptimal classes?
Related Questions in PRIMS-ALGORITHM
- Prims minimum spanning
- Bug inside Prim's MST algorithm in Java using Adjacency Matrix
- "How to Highlight Minimum Spanning Tree in Pyvis Network Graph when Extracting Minimum Spanning Tree using Prim's Algorithm?"
- Prim’s MST Algorithm
- pq Undeclare identifier
- How to calculate the complexity of Prim's Algorithm when using HashMaps
- Operating on a pair of elements in an array and dropping one
- JavaScript method not saving the return values on initial run
- Error in Wikipedia pseudocode for Prim's Algorithm?
- Prim's algorithm providing inconsistent results
- how to program Prim's and Kruskal's algorithm using adjacency lists in C
- Prim's MST implementation with priority queue error
- Why is my Prim's algorithm not returning the proper MST?
- How to show float value instead of 0 integers
- How create an adjacency matrix of a Maze graph
Related Questions in SPANNING-TREE
- Jgrapht: how to convert a directed cyclic graph into a DAG?
- What does an illustrated undirected graph with only 1 endpoint look like?
- is it possible to find a spanning tree for a direct and unweighted graph?
- Linear Time Algorithm to Find MST?
- Is the computed number of spanning trees for this undirected graph reasonable/correct?
- How is a cut lonely if there are often multiple edges crossing a cut in a connected undirected graph?
- Spanning Trees in Answer Set Programming
- How to generate and plot all spanning trees?
- Time Complexity of (Minimum Spanning Tree) Prim's Algorithm
- Edmond maximum branching algorithm
- Difference between prims and boruvka's Algorithm
- Ne04j Graph Nodes, Expand a spanning tree but stop at specific node (but don't stop for other nodes)
- How to find a spanning tree of a undirected graph(not necessary MST)?
- Minimum spanning trees of sub-graphs?
- Counting spanning trees in a graph
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
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.