Skip to main content
RISC
  • Home
  • More
English ‎(en)‎
Deutsch ‎(de)‎ English ‎(en)‎
You are currently using guest access
Log in
RISC
Home
Expand all Collapse all
  1. PractSoftTech15
  2. Exercises
  3. Exercise 9 (Graphs) - Deadline is June 12th

Exercise 9 (Graphs) - Deadline is June 12th

Completion requirements
Opened: Thursday, 28 May 2015, 12:00 AM
Due: Saturday, 13 June 2015, 8:00 AM

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.


    You are currently using guest access (Log in)
    Data retention summary
    Get the mobile app
    Powered by Moodle