3

The following is the given algorithm for finding a Euler Path in a Eulerian Graph. However, it is said that there is an counter example with less than 10 vertices. The given Eulerian Graph is undirected and every vertex has even degree and it will start and end at the same vertex.

1. Perform a DFS traversal of G and number the vertices in DFS-preorder.
2. Re-initialize all vertices and edges of G as unused.
3. Produce a cycle as follows:
    Start from the vertex with preorder number 1 (computed in step 1), and
    repeatedly go to the vertex with highest preorder number possible along 
    an unused edge.
    Stop when all edges incident to the current vertex are used.

I have been trying vertices from 6 to 9 for the last 3 days and I really couldn't come up with one example. Any help is appreciated! Thank you.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
swordgit
  • 115
  • 10
  • What makes you think there is a counter-example? By 'Eulerian Graph', do you mean a graph which has an Euler Path or an Euler Cycle? – Codor Apr 02 '17 at 18:54
  • @Codor Thanks for replying. By Eulerian Graph, it means that every vertex has a even degree. There should be a counter-example given that the hint said the counter example has less than 10 vertices. – swordgit Apr 02 '17 at 19:24
  • 1
    Ok, then I wonder what makes you think there is a counter-example; if every vertex has even degree, there is no chance of getting stuck, regardless of preference of neighbours, I believe. – Codor Apr 02 '17 at 19:27
  • Well, there _is_ a chance of getting stuck; the problem is interesting - so far, I have also failed to come up with a counterexample. It's very amazing. – Codor Apr 03 '17 at 19:29
  • well correct me if i m wrong but wont the algo be struck for A ---- B \ / C / \ D ---- E With DFS- `C A B D E` Now as `C` is node number 1 we will start from it and will have to visit it again to go to other cycle. Similar examples with 2 or more cycles with common node will give error if what i understood of your code is correct. – monster Apr 04 '17 at 09:17

2 Answers2

1

It's a little pedantic based on the definition that a Euler graph is a graph where each vertex has even degrees, so what if we considered that the graph was unconnected?

A---C   E---G
|   |   |   |
B---D   F---H

To run DFS on different components - there would need to be a step prior to #1 which discovers the complete graph.

The following graph would also not work as the algo would take the path: {0,3,4,7,1,3,2,1,0} missing 5,6.

graph

Elliott de Launay
  • 1,027
  • 13
  • 31
0

I am posting this as an answer because I didnt know how to show the graph correctly in comment as you could have seen.

Well correct me if i m wrong but wont the algo be struck for following graph- 

 A---B
  \ /
   C 
  / \
 D---E

With DFS- C A B D E

Now as C is node number 1 we will start from it and will have to visit it again to go to other cycle.

Similar graphs with 2 or more cycles with common node will give error if what i understood of your code is correct.

PS- Can anyone tell how start newline in comment

monster
  • 808
  • 10
  • 23
  • 2
    I'm not sure I understood your point correctly; starting at `C` and using the given DFS sequence, the proposed algorithm succeeds. – Codor Apr 04 '17 at 13:20