2-Colorability
If you can color a graph using only 2 colors such that no two adjacent nodes have the same color, it is bipartite.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
A graph is bipartite if its vertices can be divided into two independent sets such that no two vertices in the same set are connected.
If you can color a graph using only 2 colors such that no two adjacent nodes have the same color, it is bipartite.
A graph is bipartite if and only if it contains no odd cycles (cycles of length 3, 5, 7, etc.).
We use BFS to assign alternating colors to nodes. If we ever find an edge between nodes of the same color, the check fails.
Bipartite graphs are used in matching problems, job assignments, and representing relationships between two different types of entities.