Problem set: Bipartite graphs

Problems::
(1) Give an algorithm that bipartises a graph G if possible, else returns failure
(2) P.T. a bipartite graph G with odd number of vertices is nonhamiltonian
(3) Give an algorithm to determine the hamiltonian path in a directed, acyclic graph

Solutions::
(1) Algorithm to bipartise a graph G: If the graph is bipartite, the algorithm divides the set of vertices V into two groups V1 and V2 such that all edges of G have one endpoint in V1 and another in V2. If not, the algorithm returns failure.

Initial conditions:
V1={}, V2={}
label(v) = 2, for all vertices v

Algorithm:
----------
add any vertex v from V to the queue Q
add v to V1
label(v) = 0

while(Q is not empty)
remove a vertex v from Q
for each vertex w adjacent to v
  if label(v) == label(w) /* v and w belong to the same vertex set */
      return failure
  else
      if label(w) == 2
      add w to the vertex set not containing v
      enqueue w in Q
      label(w) = 1 - label(v)
  endif
  endif
endfor
endwhile

return success

Running time of the algorithm is O(n^2) since it has to traverse all the edges of the graph.

(2) P.T. a bipartite graph G with odd number of vertices is nonhamiltonian:
Proof:
This is quite a simple proof.

Suppose n1 and n2 are the number of vertices in the two vertex sets V1 and V2 of the bipartite graph. Since, the number of vertices is odd, either n1 is greater than n2 or n1 is less than n2. Without loss of generality, suppose n1 > n2. Further suppose that the graph is such that there exists a path that starts from a vertex in V1 and alternately visits vertices from V1 and V2. Such a path will end at a vertex in V1 after having visited all vertices in V2. However, since n1>n2, one or both of the following may hold:
(a) the ending vertex is not the same as the start vertex, or,
(b) all vertices in V1 are not visited by the path.

Therefore, such a path that visits all vertices and is also a cycle cannot exist. Hence, a bipartite graph with odd number of vertices is nonhamiltonian.

Bipartite graph with even number of vertices: What happens if the graph has even number of vertices ? Suppose that this is the case and |n1|=|n2|. Also, further suppose that each vertex has even degree. In this case, is the graph necessarily hamiltonian ? The answer is no. This is because, at first glance it appears that either a hamiltonian cycle exists or there are disjoint cycles in the graph. This needs to be probed further.

(3) Give an algorithm to determine the hamiltonian path in a directed, acyclic graph
Algorithm: Initiate a DFS keeping a count of the number of vertices visited along the depth-first path so far. Also, label the current vertex with the current count. When this count becomes equal to the number of vertices of the graph, n, return success. On success, the vertices have been enumerated in an order that indicates their order along the Hamiltonian path. These can then be printed out in this order. Alternatively, an ordered list of vertices could be maintained. Also, if count never becomes equal to n, then return failure.

Further, a directed, acyclic graph will necessarily have at least 1 vertex with indegree 0 (this can also be proved). If the graph has 2 or more such vertices, then no hamiltonian path exists. If there is only 1 such vertex, then DFS may be initiated from such a vertex. This optimization can be used although it is not used in the algorithm outlined below.

Algorithm:
----------
label(start) = 1
label(v) = 0, for all other vertices v

hampath(start)
   status = find_hampath(start, 1)
   if status == true
           print_hampath(start, 1)
   endif
end hampath

find_hampath(vertex v, int count)
   label(v) = count
   if count==n
           print "hampath found"
           return true
   endif

   for each vertex w adjacent to v
           if label(w) == 0
                   flag = find_hampath(w, count+1)
                   if flag == true
                           return true
                   endif
           endif
   endfor
   return false
end find_hampath

print_hampath(vertex v, int count)
   print v
   for each vertex w adjacent to v
           if label(w) == count+1
                   print_hampath(w, count+1)
           endif
   endfor
end print_hampath