2
$\begingroup$

Given a list of edges such that the undirected graph generated cannot have multiple edges but can have loops. How many connected components can be found?

This is best demonstrated with an example. Given this list of edges:

A -- A
A -- B
B -- C
B -- D
B -- F
G -- H
H -- I
I -- G

There are two connected components that can be found:

enter image description here

Is there a way to determine how many connected components can be found without actually constructing the graph?

$\endgroup$
13
  • $\begingroup$ What kinds of graphs are you thinking of? Simple graphs? Also, are you only allowed to consider graphs with these eight exact vertices? $\endgroup$ Commented Oct 19, 2019 at 16:40
  • $\begingroup$ @TeddantheTerran I'm not familiar with graph theory terminology yet, so forgive me if I don't answer well. I'm considering any number of vertices. Just given list of edges where the number of edges is any positive number. These are directed graphs, so I don't think they are considered simple, no. I have an image of my example graph in my question if that helps. $\endgroup$
    – Peter Tran
    Commented Oct 19, 2019 at 16:47
  • $\begingroup$ No problem! But if you allow any set of vertices that includes A, B, C, D, F, G, I, and H, then there are infinitely many graphs that satisfy your conditions, so there must be some kind of restriction. $\endgroup$ Commented Oct 19, 2019 at 16:54
  • $\begingroup$ I'm not sure I understand. Could I just add vertex X to your picture without any edges? Would that count? Could I add some extra edges? Or do you want a digraph with exactly these vertices and exactly these edges? $\endgroup$
    – saulspatz
    Commented Oct 19, 2019 at 16:56
  • $\begingroup$ @saulspatz Yes, if you were to add a vertex X without any connections, or even something like $X \to Y$, then there would be 3 graphs in that case. Maybe I'm misinterpreting what the term graph means. Really I'm just interested in how many different sets of connected vertices are there. $\endgroup$
    – Peter Tran
    Commented Oct 19, 2019 at 17:09

1 Answer 1

1
$\begingroup$

I ended up using a depth first search approach to solving this:

a) Pick a random node and mark as visited
b) Find all nodes adjacent and repeat algorithm on each
c) If no adjacent nodes are found, exit

d) Increment component counter by 1
e) Repeat algorithm if not all nodes in the list have been visited

This isn't a mathematical solution as I had hoped for, but it works.

$\endgroup$

You must log in to answer this question.

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