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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – knucklebumpler
    Apr 6, 2011 at 10:33
  • $\begingroup$ @knucklebumpler, I've edited the question. sorry for the poor wording. $\endgroup$
    – Graviton
    Apr 6, 2011 at 10:35
  • $\begingroup$ @Zach, from what I know, connected component works for directed graph, not undirected graph, don't you think so? $\endgroup$
    – Graviton
    Apr 6, 2011 at 11:22
  • $\begingroup$ (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. $\endgroup$
    – Zach Langley
    Apr 6, 2011 at 11:25

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .