I have an exam next week and I found a question that I have difficults to solve:
Given the following:
Input: Simple undirected graph $G(V, E)$.
Output: Find an odd-length cycle in $G$ or show a message that all the cycles are even-length.
Suggest an algorithm to do so.
Can you please give me some ideas to do so? Please don't give me the full answer, just a direction.
Thanks!
On
I can't speak about finding an algorithm with the best runtime, but I can suggest something that works eventually.
Are your vertices numbered? If not, can you number them?
My suggestion is to start with the first vertex, then using recursion, go to the next adjacent vertex of least index and increment a counter. If this vertex has an edge to where you're started, and the counter is even, you're done. If not, continue. Repeat for all vertices, and if this fails, then there are no odd cycles.
On
Some useful properties : http://en.wikipedia.org/wiki/Bipartite_graph#Properties
A graph is bipartite if and only if it has no odd cycle.
Also, a graph is bipartite if and only if it is 2-colorable.
The rest is up to you :)
If you wanted to find just a cycle, you'd use something like BFS or DFS, marking nodes as "visited" as you touched them. Coming back to a visited node means you've found a cycle.
For your problem, coming back to a visited node whose "edge distance" is odd ("edge distance" being the number of edges in the path you've taken) means you've found an odd-length cycle. Can you think of a way to enhance the label-markings to easily detect this?