Bipartite Graphs

Math for CS · Axiom Academy

Two-colorable graphs and matching problems Informally: you can color every vertex either red or blue such that no edge connects two vertices of the same color. This is called a 2-coloring . The Odd Cycle Characterization This is the fundamental theorem of bipartite graphs. If there is a cycle of odd length, you cannot 2-color it — try alternating colors around the cycle and you will find a conflict at the last vertex. Testing Bipartiteness with BFS We can test whether a graph is bipartite in O(n + m) time using a modified BFS that attempts to 2-color the graph. Job assignment: Workers on one side, tasks on the other. Edges mean "qualified for." Student-course enrollment: Students on one side, courses on the other. Recommendation systems: Users on one side, products on the other. Edges are purchases or ratings. Stable matching: Men on one side, women on the other (Gale-Shapley algorithm). Conflict-free scheduling: Time slots vs. events, where edges represent feasible assignments. Finding a maximum matching in bipartite graphs is a classic problem with efficient solutions. The Hungarian algorithm runs in O(n^3) , and the Hopcroft-Karp algorithm achieves . In words: every subset of workers must collectively be qualified for at least as many tasks as there are workers in the subset. If any group of k workers is only qualified for fewer than k tasks, a perfect matching from U is impossible. Properties of Bipartite Graphs Every tree is bipartite (trees have no cycles at all)

This is the written version of the interactive lesson above. See the full Math for CS course.