CPS420

W2017 Assignment 2

Ryerson University

Worth: 10%

Graph Theory

Due: Monday March 27


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 Kn or Km,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 Kn, and with n vertices labeled numerically on top and m vertices labelled alphabetically underneath for Km,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 Km,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

  1. 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.

  2. 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.

  3. Upload your Graph.java to the scs moons and test it there as described on the Part B test page

  4. 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


This page is maintained by Sophie Quigley (cps420@scs.ryerson.ca)
Last modified Thursday, 23-Mar-2017 00:09:47 EDT