Exercise 9 (Graphs) - Deadline is June 12th

Determine if a given Undirected Graph is Bipartite

• An undirected graph \(G=(V,E)\) is bipartite if \(V\) can be partitioned into two sets \(X\subseteq V\) and \(Y=V\setminus X\) such that every edge in \(G\) has one end vertex in \(X\) and the other in \(Y\).
• Design an algorithm for determining if an undirected graph \(G\) is bipartite.
• Download the source code AdjacencyMapGraph.java from the Moodle page.
• Implement a method isBipartite() which returns true or false.
• Write a short documentation (txt or pdf) how the algorithm works.
  

Hints

A graph is bipartite if and only if it does not contain a cycle with an odd number of vertices. You can use a depth-first search algorithm.