3
$\begingroup$

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?

  • 0
    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.2011-04-06
  • 0
    @knucklebumpler, I've edited the question. sorry for the poor wording.2011-04-06
  • 0
    @Zach, from what I know, connected component works for directed graph, not undirected graph, don't you think so?2011-04-06
  • 0
    (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.2011-04-06

1 Answers 1

3

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