Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an undirected graph $G$, with edges $E$ and vertex $V$, how to group the edges into different sets, in which

  1. One edge can only belong in one set
  2. Every edge must be covered in one of the sets
  3. If I can "walk" from one edge to another, these two edges must be contained in a single set.

Take this for an example, I have the following edges $(A,B), (C,B), (D,B),(B,G), (E,F)$, then there are two sets, namely, $(A,B), (C,B), (D,B),(B,G)$ and $(E,F)$.

Edit: My hunch tells me that there is a standard algorithm (with a name) for this, what is it?

share|improve this question
    
I haven't studied graph theory but 1 and 2 don't make sense. It seems like they're two ways of saying the same thing, "each edge can only belong in one set", i.e. a partition on E. I just point this out because somebody that can help you might be confused too. If it's standard terminology please just excuse me. Condition 3 just defines an equivalence relation assuming that you allow a walk from an edge to itself of zero steps. –  knucklebumpler Apr 6 '11 at 10:33
    
@knucklebumpler, I've edited the question. sorry for the poor wording. –  Graviton Apr 6 '11 at 10:35
    
@Zach, from what I know, connected component works for directed graph, not undirected graph, don't you think so? –  Graviton Apr 6 '11 at 11:22
    
(I posted my comment as an answer now.) Connected components exist in both directed and undirected graphs. Directed graphs, however, distinguish between "weakly" connected components and "strongly" connected components. –  Zach Langley Apr 6 '11 at 11:25
add comment

1 Answer

up vote 3 down vote accepted

It sounds like you are just looking for connected components, which can easily be found with a simple breadth- or depth-first search.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.