2
$\begingroup$

I'm trying to find out how many circuits exist in a graph $G$, given its adjacency matrix.

Yet, the only thing I know is how to find out if there is a circuit in a graph $G(X,U)$ given a list of out-neighbours for each vertex. To do that, you just delete every vertex with no out-neighbours, and update the adjacency lists for the remaining vertices. If repeating this operation deletes all the vertices, the graph had no circuit; otherwise, it has a circuit.

For example,

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline a & b,c,d\\ b & d,e\\ c & d,f \\ e & d,h \\ f & g,i \\ g & h, e \\ h & \emptyset\\ i & g,h \\ \end{array}

Whenever $\Gamma^+(x)$ is empty, we can delete $x$.

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline a & b,c,d\\ b & d,e\\ c & d,f \\ e & d,\not h \\ f & g,i \\ g & \not h, e \\ \not h & \not\emptyset\\ i & g,\not h \\ \end{array}

Therefore, a circuit exists in $G$.

Yet, it only tells me if there is a circuit in my graph. How may I find all circuits?

for instance with: graph with nine vertex

$$\begin{bmatrix} 0 & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ b & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ c & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ d & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ e & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ f & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ g & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ h & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ i & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{bmatrix} $$

What algorithm should I use to find all the circuits of this graph? Even a hint would be appreciated.

$\endgroup$
8
  • 2
    $\begingroup$ OK, now I understand most of what you're asking -- we just need to work out exactly what you mean by "circuit". (I guess the difficulty comes from translating from another language. Graph theory is full of words that sound the same "path", "walk", "trail", "circuit", "cycle", ... and different authors don't always agree on what each of those words means, even in one langauge! $\endgroup$ Sep 27, 2015 at 10:50
  • 3
    $\begingroup$ So, it sounds like a circuit for you is a list of vertices $v_1, \dots, v_k$ such that $v_iv_{i+1}$ is an edge for each $i\in\{1, \dots, k-1\}$ and $v_kv_1$ is an edge. If so, which of the following extra conditions do you require? (a) No vertex can be in the sequence more than once; (b) no edge can be there more than once; (c) every vertex must be in the sequence; (d) every edge must be in the sequence? $\endgroup$ Sep 27, 2015 at 10:53
  • $\begingroup$ By the way, I removed the parts of the question that specify the algorithm should use an adjacency matrix rather than lists -- it's easy to convert between the two formats so any algorithm that works for lists can easily be made to work for matrices. $\endgroup$ Sep 27, 2015 at 10:54
  • $\begingroup$ Ouch! Okay, here is the definition I use: a "circuit" is consecutive arcs (path) of which both ends are the same. A "circuit" is the oriented equivalent of a "cycle" in non-oriented graphs. I'm going to edit with this definition. I will remind this next time I ask a question in graph-theory! $\endgroup$ Sep 27, 2015 at 10:57
  • 1
    $\begingroup$ If you have the adjacency matrix, you can compute the lists and vice-versa. $\endgroup$ Sep 27, 2015 at 11:06

0

Browse other questions tagged or ask your own question.