notebook.community

Edit and run

Bipartite Graph

Definition graph G is called bipartitie, if the nodes can be placed in two disjoint sets $V_1$ and $V_2$.

Detecting if a graph is bipartite or not?

  • Using breadth-first traversal
  • Start with any random node
  • Place the current node into a set (color blue)

  • The adjacent nodes of the current node cannot be placed in the same set as current node

  • Alternating colors





In [ ]:

Content source: mirjalil/DataScience

Similar notebooks:

notebook.community | gallery | about