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
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
http://www.cs.sunysb.edu/~algorith/files/graph-isomorphism.shtml
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.
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 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
http://en.wikipedia.org/wiki/Shortest_path_problem
where a cycle is detected any time there are multiple paths between nodes
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
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...
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
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.
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?
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
[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]
$paths[1]{$_->[1]}{$_->[0]
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
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
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
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.
>>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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
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.
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.