CODEWITHSUNDEEP
algorithmgraphbipartite
Kisegi
Kisegi

Reputation: 23

How can i prove that a graph is bipartite?

I know the theory and the lemma that says if a graph contains an odd length cycle then it cant be bipartite but how can i PROVE it?

take for example this adjacency matrix how can i prove that this graph is or isnt bipartite?

Upvotes: 1

Views: 507

Answers (1)

RBarryYoung
RBarryYoung

Reputation: 56735

So here's the algorithm I would use. It uses approach (3) that I mentioned in the comments above: determine the two sets and confirm that they meet the requirements (i.e., each vertex only connects to the other set)

  1) Make two sets, group1 and group2.  
     Mark all of the vertexes as unassigned and incomplete

  2) Assign the first unassigned vertex to group1 and make it the current vertex

  3) For every assigned vertex connected to the current vertex (both to and from):
    a) If the current vertex is unassigned, 
           then assign the current vertex to the other group
    b) If the current vertex is assigned to the same group, 
           then the graph is not bipartite, EXIT

  4) If the current vertex is still unassigned then assign it to group1
  5) For every unassigned vertex connected to the current vertex (both to and from):
    a) assign it to the other group
  6) Mark the current vertex as complete

  7) Make the first incomplete assigned vertex the current vertex
    a) If there are none, then make the first unassigned vertex the current vertex
    b) If there are none, then the graph is bipartite.  EXIT

  8) GoTo (3)

If you use the Adjacency Matrix then this is probably O(v^2) where v is the number of vertices. If you change it to a list of vertices with To/From connection lists attached then I think that it is O(v+c) where c is the number of connections.

Upvotes: 2

Related Questions