MTH 607 Graph Theory Assignment 1

General

For this assignment you must implement the bipartition algorithm. A description of this algorithm can be found in the Algorithms Handout.

Read the Preamble for information on the assignments and how to handle the input files.

Name

Your submitted file must be called bipartite.c.

You should submit your file using the command
submit-mth607 bipartite.c
on jupiter.

Input

The input will be a (di)graph. (See the preamble for information on how the graph should be input and its format.)

Return Value

Your graph should return 0 if the input graph is not bipartite, 1 if it is and -1 on an error.

Output

In addition to the return value, your program should print, using printf, a list of the vertices in each part in ascending order. The vertices should be separated by spaces, the two parts by a newline (\n). For example for the 6 cycle (0, 1, 2, 3, 4, 5) the output would look like:
0 2 4
1 3 5

The order of the vertices should be the same as in the adjacency matrix obtained from the input file, starting from 0.

Notes

Your program should be able to deal with digraphs and non-simple graphs.

Maintained by: P. Danziger, January 2008