cut-set of a graph
I just had one confusion regarding cut-set that the definition of cut-set says that it is the minimal set of edges whose removal from a graph disconnects the graph and increases the number of connected components by 1.
Now,the point of confusion lies here that why do we say that the number of connnected components increase by 1,since there can be many edges whose removal can lead to more than 2 disconnected components,so even if we say minimal there can be cases when actually removing some edges would increase the number of connected components more than by 1.
Also,one query regarding the rank of the graph which is calculated as n-k where k are the number of connected components in the graph,so in a graph the number of connected components in a connected graph always remains 1,so why then a usage of the term k.
Now,the point of confusion lies here that why do we say that the number of connnected components increase by 1,since there can be many edges whose removal can lead to more than 2 disconnected components,so even if we say minimal there can be cases when actually removing some edges would increase the number of connected components more than by 1.
Also,one query regarding the rank of the graph which is calculated as n-k where k are the number of connected components in the graph,so in a graph the number of connected components in a connected graph always remains 1,so why then a usage of the term k.
Replies
-
ManojKiran EdaI am also having the same problem...can any one please clear it. -
pratap singh, upendra
When you try to find the cut set of the graph, you subconsciously focus on one component of the graph and that's what you are supposed to do. Taking this component, you remove one edge and see if this component breaks into two sub-components. Is yes, then the removed edge becomes the cut set. If no, then you remove another edge to see if the component breaks. You continue until component actually breaks. The set of removed edges become the cut set.radha gogiaI just had one confusion regarding cut-set that the definition of cut-set says that it is the minimal set of edges whose removal from a graph disconnects the graph and increases the number of connected components by 1.
Now,the point of confusion lies here that why do we say that the number of connnected components increase by 1,since there can be many edges whose removal can lead to more than 2 disconnected components,so even if we say minimal there can be cases when actually removing some edges would increase the number of connected components more than by 1.
Sometimes you begin at a site(say site 1) and then you realize that starting from this site, it is not possible to define a cut set. Then you switch to some other site(say site 2) and start removing edges around this site. Before you start removing edges from site 2, you have to put all removed edges of site 1 back in their position.
This will ensure that a cut set causes an increase in the number of components by 1 only.
Note that site 1 and site 2 belong to the same component.
You are reading an archived discussion.
Related Posts
CEans, we are super excited to announce the winners of the Engineering For Change In India contest. We've posted a clarification for several of you who expressed concern over the...
guys m in 2nd year electrical engineering student.Iwould like to knw what to do after completion of engineering so that i can start preparing from now onwards.abroad courses are most...
CEans,
Few weeks ago, we decided to design and launch the CrazyEngineers T-Shirts and were first two batches were sold out in just few days. A lot of you asked...
The Taiwanese company, which was in a long hibernation, is now back in the Indian smartphone market. The company has launched two new mid-range smartphones, the Liquid E700 and the...
Blackphone, one of the first companies to launch privacy focused smartphones for the public has announced that it will be launching the world’s first privacy focused app store and an...