bipartite graph

A bipartite graph is a graph (in the graph theory sense) where the vertices can be divided into two sets A and B, where every vertex in A does not have an edge to any other vertex in A, and any vertex in B does not have an edge to any other vertex in B.

Bipartite graphs are used to solve a number of matching problems, such as maximizing matches of jobs to workers, and classes to classrooms.

The following are equivalent formulations of the definition of a bipartite graph:

1. The vertices of the graph may be partitioned into two sets A and B, with all edges of the graph go from a vertex in A to a vertex in B. (This is flyingroc's definition above, and is the most common).
2. The graph has chromatic number 2.
3. All cycles (loops) in the graph have an even length.

The proofs of the equivalences are (as per mathematical custom) left as an exercise for the inclined reader.

As part of the node your homework effort, I present an algorithm to determine whether a graph is bi-partite or not.

In scheme.

One glance should make you realize why there's no such thing as an obfuscated scheme contest.

The algorithm does a depth first search of the graph, marking each vertex with a parity. If it encounters a back-edge to a vertex of the same parity as the vertex being examined, it knows the graph is not bi-partite.

To make things clearer:

The graph is defined as an adjacency list at the top of the code

The parity is 0 if the vertex is unvisited and either -1 or 1 depending on which side of the graph it's on

/msg me with any more clarifications you want here...

---

(define adjList
 (vector
  '(3 4)
  '(3 4)
  '(4)
  '(0 1)
  '(0 1 2)
 )
)

(define parityList
 (vector
  0
  0
  0
  0
  0
 )
)

(define dfs
 (lambda (vertex parity)
  (define bp #t)
  (vector-set! parityList vertex parity)
  (for-each
   (
    lambda (adjVertex)
     (cond
      ((= (vector-ref parityList adjVertex) 0)
       (set! bp (and bp (dfs adjVertex (* parity -1))))
      )
     ((= (vector-ref parityList adjVertex) (vector-ref
parityList vertex))
       (set! bp #f)
      )
     )
  )
   (vector-ref adjList vertex)
  )
  bp
 )
)

(if (dfs 0 1)
 (display "Graph is Bi-Partite.\n")
 (display "Graph is not Bi-Partite.\n")
)