1. Write a program that takes the adjacency-list representation of an undirected graph G = (V, E) and prints an Eulerian cycle (or non-Eulerian if no such cycle exists) in linear expected time.

Your program should first convert each vertex’s adjacency list into a doubly-linked list (store the pointers to the heads in an array), and add each edge in G to a map.  Given an edge e = (u, v) in E, the map should return a pointer to the list node storing v in u’s adjacency list and a pointer to the list node storing u in v’s adjacency list. This way, you can delete e from G in expected constant time (assuming your map is implemented reasonably well) by deleting those two list nodes. You can use Java’s built-in Map class if you want.

Start at the beginning of the first adjacency list and walk around the graph until you get stuck, deleting from G each edge you cross and always leaving the vertex v you’re currently visiting by crossing the first edge remaining in v’s adjacency list. If you get stuck somewhere other than where you started then, as we saw in the first class, G cannot be Eulerian. If you get stuck back where you started, then the edges you’ve removed form a cycle in G. As you go, add the label of each vertex you visit to yet another doubly-linked list, L.

For example, if G is the graph on the left below and it’s given as the the set of adjacency lists in the center below, then you’ll start at 1 and visit 11 and 4, in that order, before returning to  1 and getting stuck.  When you get stuck, L will contain  1, 11, 4, 1, in that order; the adjacency lists with (1, 11), (4, 11), (1, 11) deleted are shown on the right below.

1

11

7

8

3

10

1)    11, 4

2)    8, 9, 11, 4

3)    5, 9, 8, 10

4)    1, 2, 11, 5, 9, 7

5)    4, 9, 7, 3

6)    8, 11

7)    4, 5

8)    6, 2, 10, 3

9)    2, 5, 4, 3

10)    8, 3

11)    4, 2, 6, 1

1)

2)    8, 9, 11, 4

3)    5, 9, 8, 10

4)    2, 5, 9, 7

5)    4, 9, 7, 3

6)    8, 11

7)    4, 5

8)    6, 2, 10, 3

9)    2, 5, 4, 3

10)    8, 3

11)    2, 6

Starting at the beginning of L, walk along it until you find a vertex which still has edges incident to 11.  Starting at that vertex, walk around the remainder of G until you get stuck again, deleting edges as you cross them and inserting the labels into L as if you’d interrupted your first walk, performed this new walk, and then finished your first walk.  (Again, if you don’t end up back where you started, then G cannot be Eulerian.)  This way, L ends up containing the labels of the vertices in a walk that combines both walks.  Note that vertices can appear several times! Eventually, each vertex will appear once in L for each incident edge it had in G originally.

In our example above, 1 has no more edges incident to it, but 11 does.  The first edge in 11’s remaining adjacency list goes to 2, the first edge in 2’s adjacency list goes to 8, the first edge in 8’s adjacency list goes to 6, and the first edge in 6’s adjacency list — ignoring the edge to 8 which we just crossed and deleted! — goes back to 11. After you delete the edges (2, 11) and (6, 11), there are no more edges incident to 11, so you’re stuck.  L now contains 1, 11, 2, 8, 6, 11, 4, 1 in that order.   The remainder of G and the adjacency lists are shown below; notice the missing edges are the ones you’ve crossed in your walks so far, and are the adjacent pairs in L.

11

7

8

3

10

1)

2)    9, 4

3)    5, 9, 8, 10

4)    2, 5, 9, 7

5)    4, 9, 7, 3 6)

7)    4, 5

8)    10, 3

9)    2, 5, 4, 3

10)    8, 3 11)

Again, walk along L until you find a vertex that has remaining incident edges.  (You don’t need to go back to the beginning of L, or even backward in L; indeed, doing so could make you take more than linear time.) Again, walk around the remainder of G, deleting edges and inserting vertices’ labels into L. In our example, now you start at 2 — because it’s the next vertex with incident edges in L, not because it’s the such one in numerical order!  — and walk to 9, then to 5, then to 4, then back to 2.  When you’re finished this walk, L contains 1, 11, 2, 9, 5, 4, 2, 8, 6, 11, 4, 1.

Keep going like this until there are no vertices in L with remaining incident edges. (You only ever need to walk forward in L. Why?) If you ever get stuck somewhere you shouldn’t be, G cannot be Eulerian because some vertex must have odd degree, and if there are still edges left when you’re done, G cannot be Eulerian because it isn’t connected. With our example, after another walk, L should contain 1, 11, 2, 9, 4, 7, 5, 3, 9, 5, 4, 2, 8, 6, 11, 4, 1; after yet another walk, L should contain 1, 11, 2, 9, 4, 7, 5, 3, 8, 10, 3, 9, 5, 4, 2, 8, 6, 11, 4, 1, which represents an Eulerian cycle of G.

The format of the input should be as follows: first, a line containing a number n between 2 and 1000000 indicating the size of the vertex set V = {1, . . . , n} and a number m indicating the

total number of edges (so it’s easy to set up the map); then n lines containing the adjacency lists.  Your output should be a list of the vertices’ labels as they are visited in an Eulerian cycle of G, or non-Eulerian if G is not Eulerian.

To make it easy to read the file, the first line will say n  =  ...   m  =  ..., with the dots replaced by the appropriate numbers, and the ith adjacency list will start with i, a close parenthesis, the degree of vertex i, a colon, and then the adjacency list.

INPUT:

n  =  11 m  =  19

1)  2:  11  4

2)  4:  8  9  11  4

3)  4:  5  9  8  10

4)  6:  1  2  11  5  9  7

5)  4:  4  9  7  3

6)  2:  8  11

7)  2:  4  5

8)  4:  6  2  10  3

9)  4:  2  5  4  3

10)  2:  8  3

11)  4:  4  2  6  1

OUTPUT:

1  11  2  9  4  7  5  3  8  10  3  9  5  4  2  8  6  11  4  1

INPUT:

n  =  3 m  =  2

1)  1:  2

2)  2:  1  3

3)  1:  2

OUTPUT:

non-Eulierian

You can get part marks for well-documented code even if it doesn’t work.  You may get no marks (and possibly a referral to the AIO committee) for code that works but you’ve clearly downloaded from somewhere without understanding it.

Notice I’ve changed the input format to make it easier to read!  Also, I’ve uploaded to BrightSpace a  .h file I wrote and a  .c file with the code for the basic subroutines; you just have to write the main  .c file, and maybe translate it into Java if that’s what Mimir wants.   (The sample inputs on BrightSpace are not our actual test cases.)

2. Write a program that takes the adjacency-list representation of an undirected graph G = (V, E) and prints Hamiltonian if G is Hamiltonian and non-Hamiltonian otherwise.  Your input format should be the same as for the first question. Follow the pseudo-code below (but note, for example, that you might have problems declaring visited before you read n). Your program won’t be polynomial time — so it won’t handle big graphs — but try to make it as efficient as you can (without knocking yourself out over it).

Notice  that  you   don’t   need   a   dictionary   after   all  —  just   an   array adjacentTo1[1..n] !

int  n  is  the  number  of  vertices

int  degree[1..n]  stores  the  degrees  of  the  vertices

int  **list  is  an  array  of  arrays  storing  the  adjacency  lists

boolean  visited[1..n]  is  initially  all  false

boolean  adjacentTo1[1..n]  says  whether  a  vertex  is  adjacent  to  vertex  1

void main  {

read  the  input

visited[1]  =  true

if  finishHamCycle(1,  1)  ==  true

print  "Hamiltonian"

else

print  "non-Hamiltonian"

end  if

return

}

boolean  finishHamCycle  (vertex  u,  int  visitedCount)  {

if  visitedCount  ==  n  and  adjacentTo1[u]

return  true

end  if

for  v  in  u’s  adjacency  list

if  visited[v]  ==  false

visited[v]  =  true

if  finishHamCycle(v,  visitedCount  +  1)  ==  true

return  true

end  if

visited[v]  =  false

end  if

end  for

return  false

}