What is a cycle in graph theory

[talolard]

Homework Statement

Sorry about the basic question, I haven't takena course on graph theory yet but need this for a course in computer science.
The problem: Write a program whose input is an adjecancy matrix and whose output is the number of cycles of length 3 and 4.

The Attempt at a Solution

So i figured out that raising the matrix to the nth power will give me the number of paths of length n that will take me from point a to point b.
But what is a cycle? I thought it might be the diagnol but I think I'd be counting paths that go backa nd forth between two points.
So what is a cycle, and what does it look like on a matrix?
Thanks
Tal

 

[Tinyboss]

The adjacency matrix for a graph with n vertices is an n-by-n matrix A such that [tex]A_{ij}=1[/tex] if there is a path from i to j, and zero if not. So a 3-cycle is a set of vertices a,b,c such that [tex]A_{ab}=A_{bc}=A_{ca}=1[/tex].

I haven't taken a course in this stuff, so that's all I know for sure. I don't know whether the vertices need to be distinct, though I suspect they do; else every vertex that connects to itself would form an n-cycle for all n, and every n-cycle would also be a kn-cycle for all k. But maybe that is how it's done--check your textbook.

 

[farleyknight]

Homework Statement

Sorry about the basic question, I haven't takena course on graph theory yet but need this for a course in computer science.
The problem: Write a program whose input is an adjecancy matrix and whose output is the number of cycles of length 3 and 4.

The Attempt at a Solution

So i figured out that raising the matrix to the nth power will give me the number of paths of length n that will take me from point a to point b.
But what is a cycle? I thought it might be the diagnol but I think I'd be counting paths that go backa nd forth between two points.
So what is a cycle, and what does it look like on a matrix?
Thanks
Tal

Like Tinyboss, I haven't taken a course in this either but I have been curious about graphs. Computational & computer science problems interest me a great deal.

Doing some quick sketching to review the concepts you bring up, I noticed that the number of n-cycles starting and ending with vertex v_i would correlate with the value [M^n]_{i,i}. This is a simple corollary from the fact you just stated. Being so simple, I would imagine you're looking for something more than that.

Are you looking to find out what the vertices in that cycle are? You might be able to do that with a matrix if you create elements for each edge and use a non-commutative multiplication operator. I only checked with three vertices and third power but it might work.. I dunno.

 

[farleyknight]

Okay, I just re-read your question. I think it would be the diagonal but it depends on the definition they gave. Different authors use slightly different definitions in graph theory, so it's important you get the right one:

http://en.wikipedia.org/wiki/Cycle_(graph_theory )

If repeated vertices are allowed you can use your original algorithm. Most likely that's what they want.

If not, you could convert your graph to a digraph and modify the entries of your matrix to be the edges in the graph such that (v_i, v_j) * (v_j, v_i) = 1. There's a bit more to it than that, I could go into more detail. It's just a rough idea, but I think it would work out.

 

[talolard]

Like Tinyboss, I haven't taken a course in this either but I have been curious about graphs. Computational & computer science problems interest me a great deal.

Doing some quick sketching to review the concepts you bring up, I noticed that the number of n-cycles starting and ending with vertex v_i would correlate with the value [M^n]_{i,i}. This is a simple corollary from the fact you just stated. Being so simple, I would imagine you're looking for something more than that.

Are you looking to find out what the vertices in that cycle are? You might be able to do that with a matrix if you create elements for each edge and use a non-commutative multiplication operator. I only checked with three vertices and third power but it might work.. I dunno.

Thansk eveyrone for the replies, I'm still not clear on things.

The program I am supposed to write takes as input an adacency matrix and returns the number of 3 and 4 cycles. It's nothing to complex but i am still not sure what a cycle is.
As was stated, it seems to me that a cycle of length n woudl register on the diagnol of the matrix of the nth power. But i think that leads to "counting" the same cycle a few times. For instance if you havea cycle the goes from A to B to C to A then the duagnol will have a 1 but it will be the same cycle So you need to count it only once. But it gets more complicated if you have for instance a 5x5 matrix and you are looking for 3-cycles.

Sample input:
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

The out put should be: The number of 3 cycles is 2
the number of 4 cycles is 3.
But when i raise it to power the diagnal shows somethign else.
Thanks
tal

 

[talolard]

Here is a guess:
The number of different cycles of length n are the number of different non zero valus on the diagnol. This is just a guess but it works for the sample input:
The third power of the matrix
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0
is

4 5 7 2 7
5 4 7 2 7
7 7 2 6 2
2 2 6 0 6
7 7 2 6 2

Which has two non zero values on the diagnol (4 and 2)
the fourth power is
19 18 11 14 11
18 19 11 14 11
11 11 20 04 20
14 14 04 12 04
11 11 20 04 20
Which has three different values on the diagnol (19, 20 12)

Any thought on this?

 

[farleyknight]

In the link I posted, there are 8 or 9 variations on the same basic definition. In some cases, a cycle is allowed to repeat vertices, but a circuit is not. This is actually a problem with the field of graph theory and most authors take the time to define their words carefully since there isn't a consensus on what the definitions are. You should double check with your instructor that repeated vertices are not allowed, as you state in your problem, as some definitions mentioned on the Wikipedia page state that repeats are allowed.

In particular, the third definition on that page says:

* A closed directed walk, with repeated vertices allowed. (This usage is common in computer science. In graph theory it is more often called a closed directed walk.)

If you are absolutely sure that repeats are not allowed, you'd have to do something fancier than simple A^n. Several people asking similar questions on the 'net end up with variations on the DFS algorithm, where the structure of the matrix has no relevance to the way the problem is solved. If that is the case, then you'll want to start from square one and use one of those.

Additionally, if the answers you find here don't suffice, you might want to try it on mathoverflow.net.

When I answered this question last, I started scribbling something down that used matrix multiplication but didn't have the problem you mentioned. I wondered if it was possible to use matrix operations to find the cycles of length exactly 3 or 4. I think there is a way but it involves modifying the elements of your matrix, and I suspect that is not what they are looking for. But just for fun, this is what I came up with:

Take your matrix:

0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

I would label the columns and rows by letters for each vertex

a b c d e
a 0 1 1 0 1
b 1 0 1 0 1
c 1 1 0 1 0
d 0 0 1 0 1
e 1 1 0 1 0

Then I would replace each 1 with an element like (a,b) where you match the row with the column to produce the edge (a,b). Make sure you do this in the correct order, since you are producing the underlying digraph from this graph.

So the first two rows would look like:

a 0 (a,b) (a,c) 0 (a,e)
b (b,a) 0 (b,c) 0 (b,e)
...

What use is this? Well, when you do your matrix multiplication, you want to perform + and * like this:

(a, b) * (b, c) = (a,b,c)

(a, b, c) * (c, b, b, a) = (a,b,c,b,c,a) = (a,b,c,a)

(a,b) + (a,b) = (a,b)

The * rule joins edges together to form longer walks. Reducing the walk (a,b) * (b,c) = (a,b,c) just makes it easier to read.

The rule (a, b, c) * (c, b, b, a) = (a,b,c,b,c,a) = (a,b,c,a) makes sure that hoping back and forth along the same path does not count as one long path. You'll need some function that would remove duplicates.

The rule (a,b) + (a,b) = (a,b) simply means not to count the same path twice.

When you're done, each entry should contain something like (a,b,c,a) + (a,d,a) + (a,e,d,a), which would represent the unique cycles from a back to a.

This really seems like a complication of the question your asking. The algorithm really doesn't seem like it would be very efficient, since not only are you using matrix multiplication, which isn't very fast by itself, but the reduction for each cell is non-trivial as well. I wouldn't recommend that people actually implement this ;) I just thought it was neat since you can solve this problem by creating a ring using * as string concatenation and + as disjoint sum.

 

[farleyknight]

Here is a guess:
The number of different cycles of length n are the number of different non zero valus on the diagnol. This is just a guess but it works for the sample input:
The third power of the matrix
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0
is

4 5 7 2 7
5 4 7 2 7
7 7 2 6 2
2 2 6 0 6
7 7 2 6 2

Which has two non zero values on the diagnol (4 and 2)
the fourth power is
19 18 11 14 11
18 19 11 14 11
11 11 20 04 20
14 14 04 12 04
11 11 20 04 20
Which has three different values on the diagnol (19, 20 12)

Any thought on this?

I'm not sure if that works. Imagine if we used the vertex labeling that I mention in my last post. From your matrix we have the 3-cycles a-b-c-a, a-b-e-a. If I decide to add another edge between a and d, you have another: a-d-e-a. The resulting matrix would be:

0 1 1 1 1
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
1 1 0 1 0

But that matrix to the third power gives me:

8 8 8 8 8
8 4 8 4 8
8 8 4 8 4
8 4 8 4 8
8 8 4 8 4

So it doesn't quite fit your hypothesis.