Team Size
This lab can be done in teams of 1 or 2.
Assignment Description
This assignment is in two related parts focusing on Eulerian and Hamiltonian circuits.
Part A is a written paper submission and part B involves Java programming.
Part A  Complete graphs and Euler and Hamiltonian circuits
In this part you are asked to fill out two tables. Each row is about a complete graph
K_{n} or K_{m,n}. For each such row you should do the following:
 In the second column, draw the complete K graph. The vertices have been laid out for you,
in a circular pattern for K_{n}, and with n vertices labeled numerically on top
and m vertices labelled alphabetically underneath for K_{m,n}
 In the third column either describe an Euler circuit for the K graph listing the vertices
in the order in which they will be traversed,
or explain why this graph does not have an Euler circuit.
 In the fourth colum, either describe a Hamiltonian circuit for the K graph listing the vertices
in the order in which they will be traversed,
or explain why this graph does not have a Hamiltonian circuit.
The bipartite graphs in questions 2, 4, 5 are defined
on page 641 of your textbook in Exercise 10.1.37 and also in
Wikipedia.
A complete bipartite graph K_{m,n} is a bipartite graph
with all possible edges between a set of m vertices and a set of n vertices.
Please fill out the
part A assignment sheet.
Part B  Backtracking search for Hamiltonian graphs
In this section you will write a backtracking algorithm to find a Hamiltonian circuit in a graph if
one exists or to identify when there isn't one.
To do this, you will need to make a few modifications to an existing
set of Java routines which have the following
javadoc. Note that the files are in a Java package in this javadoc,
but the source files in the handout have been removed from the package in order to simplify testing on the moons,
which is where your files will need to run.
Assignment
 Familiarise yourself with the handout Graph and Circuit classes which are described in the javadoc.
Please note that you will probably not need to use all the fields and methods that have been provided in
these two classes. They are available to make the classes more functional and to provide you with
infrastructure that you may find useful.
 Implement the getHamiltonian method of the Graph class as specified in the Javadoc.
You may add fields and additional methods to the Graph class, should you need them, but
do not modify the other existing fields and methods of Graph.java
and do not modify the other two classes, Test and Circuit.
The reason for these restrictions is that your code will be automatically graded by a script on the scs moons.
This script will use its own copy of Test.java and Circuit.java and will assume that these three classes
follow the javadoc specs. If you change the code or specs, you run the risk of having the script give you a grade of 0,
which would be a shame.
Here is a very simple backtracking algorithm to find a Hamiltonian circuit:
 Visit the first vertex
 For each newly visited vertex,
visit every one of its unvisited adjacent vertices one by one,
each time trying to complete the Hamiltonian circuit,
until you find one that works.
 Do this recursively (you will need a recursive helper function).
If you are puzzled by the recursion, take a look at the code for
the Graph.isConnected method and its recursive helper function, the Graph.DFS method,
which implements a recursive depth first search visitation of the graph.
These methods are significantly simpler than finding a Hamiltonian circuit,
but you might find them helpful to structure your recursion.
This work is not onerous: my getHamiltonian method consists of 13 lines of code,
with a helper function that is 15 lines long.
Finally, for the purposes of this assignment, you can assume that Hamiltonian graphs
need to have at least 3 vertices. This definition is technically incorrect, but it will facilitate
doing the assignment.
 Upload your Graph.java to the scs moons and test it there as described on the
Part B test page
 Submit your Graph.java file
electronically on the scs moons.
References
 Textbook chapter 10
 Handouts and other references can be found in the
Lecture Material
Hand In
