Hierholzers algorithm. Hierholzers algorithm is another algorithm for finding an Euler

Chapter 5, Problem 75

(choose chapter or problem)

Hierholzers algorithm. Hierholzers algorithm is another algorithm for finding an Euler circuit in a graph. The basic idea behind Hierholzers algorithm is to start with an arbitrary circuit and then enlarge it by patching to it a kissing circuit, continuing this way and making larger and larger circuits until the circuit cannot be enlarged any farther. (For the definition of kissing circuits, see Exercise 74.) More formally, Hierholzers algorithm is as follows: Step 1. Start with an arbitrary circuit C0. Step 2. Find a kissing circuit to C0. If there are no kissing circuits to C0, then you are finishedC0 is itself an Euler circuit of the graph [see Exercise 74(b)]. If there is a kissing circuit to C0, lets call it K0, and let V denote the vertex at which the two circuits kiss. Go to Step 3. Step 3. Let C1 denote the circuit obtained by patching K0 to C0 at vertex V (i.e., start at V, travel along C0 back to V, and then travel along K0 back again to V). Now find a kissing circuit to C1. (If there are no kissing circuits to C1, then you are finishedC1 is your Euler circuit.) If there is a kissing circuit to C1, lets call it K1, and let W denote the vertex at which the two circuits kiss. Go to Step 4. Steps 4, 5, and so on. Continue this way until there are no more kissing circuits available. (a) Use Hierholzers algorithm to find an Euler circuit for the graph shown in Fig. 65 (this is the graph model for the mail carrier in Example 14). (b) Describe a modification of Hierholzers algorithm that allows you to find an Euler path in a connected graph having exactly two vertices of odd degree. (Hint: A path can also have a kissing circuit.)