1
$\begingroup$

I am working on the problem of finding cycles in an undirected graph. I made up my solution by first detecting if any cycles are present with a DFS algorithms and detecting any backtracking, and second, recursively explore all the found backtracked edges until I find the starting vertex. The problem I have is that this approach gives additional cycles, and I don't know how I can remove them in a post-processing step.

The classical way is to represent the cycles as binary vectors, and then XOR them by pairs: if the result is equal to another cycle, then the latter can be removed.

For example, consider the following graph, that obviously has only two basic cycles:

g1

Exploring all possible cycles will give these 3:

c1: 1-2-3
c2: 2-3-4
c3: 1-2-4-3

Converting to binary vectors:

edge | c1   c2   c3
1-2  | 1    0    1
1-3  | 1    0    1
1-4  | 0    0    0
2-3  | 1    1    0
2-4  | 0    1    1
3-4  | 0    1    1

Computing $c1 \oplus c2$ will give 110011, which is equal to c3, so we can remove c3.

But in many situations, this is not enough. For example, consider the following graph, having $v=4$ vertices and $e=6$ edges.

g2

A well know result states that for a single-connected graph with $v$ vertices and $e$ edges, the number of cycles will be $c=e-v+1$, so we have 6-4+1=3 cycles in this example.

But by proceeding with my approach, I get the following 4 cycles:

c1:   1-2-3
c2:   1-2-4
c3:   1-3-4
c4:   2-3-4

If I convert them to binary vectors and XOR them, I am not able to remove the additional cycle.

edge | c1  c2  c3  c4
1-2  | 1   1   0   0
1-3  | 1   0   1   0
1-4  | 0   1   1   0
2-3  | 1   0   0   1
2-4  | 0   1   0   1
3-4  | 0   0   1   1
  • $c1 \oplus c2 = 011110$
  • $c1 \oplus c3 = 101101$
  • $c1 \oplus c4 = 110011$
  • $c2 \oplus c3 = 110011$
  • $c2 \oplus c4 = 101101$
  • $c3 \oplus c4 = 011110$

All these computations produce binary vectors with 4 '1', while all the initial cycles have 3. Thus I can remove none.

Note that this not only a matter of a (single) one additional cycle. For more complex graph (say, Petersen graph for example), I get more than one additional cycles.

I am looking for any ideas on how to remove the additional cycles.


Edit: As suggested in answer, I have build the incidence matrices for the two examples above:

          A1              A2
vert:   1 2 3 4        1 2 3 4
      | 1 1 0 0 |    | 1 1 0 0 |
      | 0 1 1 0 |    | 0 1 1 0 |
edges | 1 0 1 0 |    | 1 0 1 0 |
      | 0 1 0 1 |    | 0 1 0 1 |
      | 0 0 1 1 |    | 0 0 1 1 |
                     | 1 0 0 1 |

Edit 2 For A2, I computed the Reduced Echelon Form (that I understand is useful to find the solutions to $AX=0$):

$A2 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$

But this stills end up with a null vector...

$\endgroup$
  • $\begingroup$ Additional detail: I don't want to rebuild graph theory ;-) I am just looking for a way to make my implementation work, and I have the feeling that I missed something. $\endgroup$ – kebs Dec 7 '17 at 9:17
2
$\begingroup$

Consider the incidence matrix of your graph, which is the $E \times V$ matrix in which each row contains exactly two 1s, corresponding to the vertices constituting the given edge, and the rest of the entries are 0. We think of the entries as belonging to $\mathbb{Z}_2$. A set of edges is in the left kernel of the matrix iff it is an XOR of cycles; it is known as the cycle space of your graph. You can find a basis for the cycle basis by finding a basis for the left kernel (this is an exercise in linear algebra). The basis will contain $|E|-|V|+c$ elements, where $c$ is the number of connected components.

If you don't like XOR, you can instead orient your edges arbitrarily, and then use the orientation to form a matrix in which each row contains one $1$ entry and one $-1$ entry. The left kernel of the matrix over the integers is known as the integral cycle space (also described in the link above), and it consists of sums (with integer coefficients) of cycles, where now a cycle is a sum of edges, some of which are possibly negated so that the orientations match.

$\endgroup$
  • $\begingroup$ Thanks for your answer ! I will carefully read that, not sure to get all the aspects at present, I might need some more clarifications, I'll tell you. I had of course see that WP page, but didn't really get the point. Now it might be clearer. $\endgroup$ – kebs Dec 8 '17 at 7:12
  • $\begingroup$ I think a need some more clarifications. If I understand correctly, you propose above two approaches for solving, the first one using XOR, the second without. At present, and as I do like XOR ;-), lets stick with the first. $\endgroup$ – kebs Dec 9 '17 at 10:10
  • $\begingroup$ I'm ok with building the matrix (see edit) but I don't understand next step. If I try to find $x$ for $x^T A = 0^T$, I get a null vector... What did I miss ? $\endgroup$ – kebs Dec 9 '17 at 10:11
  • $\begingroup$ You need to find all solutions to that equation, or rather, a basis for the space of all solutions. That requires some linear algebra. $\endgroup$ – Yuval Filmus Dec 9 '17 at 10:17
  • $\begingroup$ Thanks, but... could you elaborate ? You mean there is another solution than the null vector ? How do I compute that ? I build the RRE form for A2 (see my edit), but I have the feeling this leads me nowhere... $\endgroup$ – kebs Dec 10 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.