[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1780
  • Last Modified:

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
0
xRalf
Asked:
xRalf
1 Solution
 
xRalfAuthor Commented:
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.
0
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
ozoCommented:
Are you talking about a directed graph?
If so
http://www.cs.utk.edu/~parker/Courses/CS302-fall05/Notes/GraphIntro/
0
 
ozoCommented:
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
0
 
xRalfAuthor Commented:
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
0
 
TalmashCommented:
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...
0
 
ozoCommented:
Yes, a cycle is detected any time there are multiple paths between nodes
0
 
xRalfAuthor Commented:
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.
0
 
ozoCommented:
If you have a fully connected graph on 8 nodes, would you want to count 2520 cycles of length 8?
0
 
ozoCommented:
>  graphs.bmp
Will all the node have degree (exactly/no more than/no less than) three?
0
 
ozoCommented:
@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
0
 
xRalfAuthor Commented:
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.
0
 
ozoCommented:
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
0
 
xRalfAuthor Commented:
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.
0
 
ozoCommented:
To prove that graphs are isomorphic, it is sufficient to show a bijection that makes them identical.
To prove that graphs are not isomorphic, it is sufficient but not necessary to show that one graph has a different number of cycles than another.
Looking at a form of the graphs that make their bipartite nature obvious may make it easier
to transform them in ways that make the differences or similarities more obvious.
You may be able to enumerate all C4 cycles by hand in 30 minutes, but to prove that you have not missed any you may need to display all intermediate steps of finding an exhaustive list of paths of length <=4
0
 
xRalfAuthor Commented:
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?
0
 
JimFiveCommented:
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
0
 
xRalfAuthor Commented:
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.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now