Link to home
Start Free TrialLog in
Avatar of xRalf
xRalf

asked on

Searching cycles in graph

Hello,

I often have to solve examples of searching isomorphisms in graphs.
I'm first looking for cycles of length 3 (triangles)
then cycles of length 4, 5, 6, ... and compare the graphs if the number of cycles of length N is different. And so, I can say that those graphs aren't isomorphic.
and now my question...
Do you know some algorithm how to effectively find all cycles of length N? (N equals 3, 4, 5, 6, ...).
I'm doing it with my eye and many times happens that I forget something.

thanks for help
Avatar of ozo
ozo
Flag of United States of America image

Avatar of xRalf
xRalf

ASKER

and now my question...
Do you know some algorithm how to effectively find all cycles of length N? (N equals 3, 4, 5, 6, ...).
I'm doing it with my eye and many times happens that I forget something.
Are you talking about a directed graph?
If so
http://www.cs.utk.edu/~parker/Courses/CS302-fall05/Notes/GraphIntro/
If not, you can adapt
http://en.wikipedia.org/wiki/Shortest_path_problem
where a cycle is detected any time there are multiple paths between nodes
Avatar of xRalf

ASKER

The graph is undirected.
and I'd like to find all cycles of length N in each graph.
for example: How would you find all cycles of length 6? It is easy to forget something. And that's way I'm looking for some algorithm that will guarantee it.

I attached the file graphs.bmp
graphs.bmp
you need to define "connectivity matrix" A[nxn]
1. initiate A = I[n] (main diagonal set to 1, upper and lower triangles set to zero)
2. foreach arc in the graph that connect nodes i & j , set A[i,j] = A[j,i] = 1

now the algo:
find all nodes with distance = 1 from node i = D(i,1)
find all nodes with distance = 2 from node i = D(i,2)
find nodes that belong to both D(i,1) & D(i,1) => all the circles with legth 3

and so on...
Yes, a cycle is detected any time there are multiple paths between nodes
Avatar of xRalf

ASKER

Hi Talmash,

it seems too complex. What if the length is 8? We have to try 1+7, 2+6, 3+5, 4+4? And how would you count the cycles? We have to examine all of the nodes, so we could count the same cycle twice.
If you have a fully connected graph on 8 nodes, would you want to count 2520 cycles of length 8?
>  graphs.bmp
Will all the node have degree (exactly/no more than/no less than) three?
@graphsA=(
[0,1],[0,5],[0,9],
[1,0],[1,2],[1,4],
[2,1],[2,3],[2,6],
[3,2],[3,4],[3,8],
[4,1],[4,3],[4,5],
[5,0],[5,4],[5,7],
[6,2],[6,7],[6,8],
[7,5],[7,6],[7,9],
[8,3],[8,6],[8,9],
[9,0],[9,7],[9,8],
);
$paths[1]{$_->[0]}{$_->[1]}{1<<$_->[1]}=1 for @graphsA;
$paths[1]{$_->[1]}{$_->[0]}{1<<$_->[0]}==1 or die "@$_" for @graphsA;
for$l( 2..6 ){
     for $a (keys %{$paths[$l-1]} ){
      $pa=$paths[$l-1]{$a};
      for $b (keys %$pa ){
          next if $b eq $a;
          $pb=$pa->{$b};
          for $c (keys %{$paths[1]{$b}} ){
              if( $l==3 ){
                  print;
              }
              $m = 1<<$c;
              $paths[$l]{$a}{$c}{$m|$_} += $pb->{$_} for grep!($m&$_),keys %$pb;
          }
      }
   }
}
for $l (3..6){
 $n=0;
 for $a (keys %{$paths[$l]} ){
   $n+= $_ for values%{$paths[$l]{$a}{$a}};
 }
 print "length $l cycles",$n/(2*$l),"\n";
}

gets:
length 3 cycles 0
length 4 cycles 5
length 5 cycles 0
length 6 cycles 15
Avatar of xRalf

ASKER

This is the typical example on my exam. I have only a pen and a paper and 30 minutes. It would interest me how would you solve it if you don't want to forget something. The question is which of the graphs A, B, C, D are isomorphic. And the only reasonable possibility is to count the cycles of various lengths. The problem is, that it is not suffiecient to say that graph A has more cycles of length 6. We have to also say exactly how many cycles and enumerate them... This is the wish of our teacher.
Maybe coloured pens?

But two graphs can have the same number of cycles and not be isomorphic.
To find an isomorphism you can reorder the vertices so than the graphs are identical.
In the examples in graphs.bmp, you you may want to start by reordering them do show that they are bipartite graphs
Avatar of xRalf

ASKER

I'm not sure if I can use colored pens...

>>But two graphs can have the same number of cycles and not be isomorphic.

Yes. I'm first trying to find the different number of cycles of length N. Then I try to find the bijection between graphs (numbering of vertices).

>>In the examples in graphs.bmp, you you may want to start by reordering them do show that they are bipartite graphs

That's good idea. I tried it and found e.g. that A and B aren't isomorphic. But the teacher is quite strict and wants some proof (that's because I'm counting the cycles)

This is the comment from teacher: It is not sufficient to write for example that graphs contains various number of C4, you have to also write how many and which.
ASKER CERTIFIED SOLUTION
Avatar of ozo
ozo
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of xRalf

ASKER

You can notice that graphs on the picture have the same number of C4. So I would look for C5, C6, ... Is it real requirement from our teacher to show the exact differences?
To do this by hand, I wouldn't use cycles.

I would first label each graph and then write out the connections for each point
A -> B,C,D
B -> A,F,G

Then, by putting the lists next to each other it should be possible to reorder the lists and find the bijection.

Alternatively, you might try to redraw each of the graphs in a way that minimizes line crossings, For example, in your graph A1, If we label the leftmost point A and thus around clockwise. you could move point B and point J inside the circle as a first step.
--
JimFive
Avatar of xRalf

ASKER

Hi JimFive,

I don't know exactly how you mean it. Try to solve the example with your strategy and paste a result as a picture or something. It is a little different to solve it theoretically and practically.