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$

closed as unclear what you're asking by D.W. Dec 14 '16 at 9:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – David Richerby Sep 27 '15 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$ – David Richerby Sep 27 '15 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$ – David Richerby Sep 27 '15 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$ – ThePassenger Sep 27 '15 at 10:57
  • 1
    $\begingroup$ If you have the adjacency matrix, you can compute the lists and vice-versa. $\endgroup$ – David Richerby Sep 27 '15 at 11:06