Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp

3.5.17 · Coding › Graphs

1. Bipartite graph kya hota hai?

WHY care karte hain? Bahut saare real problems "do tarah ki cheezein ek saath match" hoti hain: jobs↔workers, students↔projects, left pixels↔right pixels. Bipartiteness woh structural property hai jo matching ko efficiently solve karne laayak banati hai.

2. 2-Coloring Test (bipartiteness decide karna)

First principles se derivation. Coloring ek constraint system hai: har edge demand karti hai $c_{u} \neq = c_{v}$ over ${0, 1}$ . Sirf 2 colors ke saath, " $\neq =$ " ka matlab hai $c_{v} = 1 - c_{u}$ — ek deterministic rule jab ek vertex fix ho jaaye. Toh ek connected component ke andar sirf do valid colorings hoti hain (saare colors swap karo), jo start se determine hoti hain. BFS/DFS bas yahi forced rule apply karta hai; clash ka matlab hai koi assignment exist nahi karta.

function isBipartite(G):
    color = array of -1 for all vertices   # -1 = uncolored
    for each vertex s with color[s] == -1: # handle disconnected graph
        color[s] = 0
        queue = [s]
        while queue not empty:
            u = queue.pop()
            for v in neighbors(u):
                if color[v] == -1:
                    color[v] = 1 - color[u] # WHY: force opposite
                    queue.push(v)
                elif color[v] == color[u]:
                    return false            # WHY: same color on an edge = odd cycle
    return true

Complexity: har vertex/edge ek baar touch hota hai → $O (V + E)$ .

3. Bipartite Matching — problem kya hai

Hungarian-style baseline (Kuhn's algorithm)

Bar bar free left vertex se DFS karo ek augmenting path dhundne ke liye; augment karo. $O (V \cdot E)$ .

4. Hopcroft–Karp — fast karna

HOW har phase kaam karta hai:

BFS saare free left vertices se simultaneously karo, alternating edges use karke ek layered graph (distance levels) banao. Yeh shortest augmenting distance dhundta hai.
DFS in layers ke through greedily ek maximal set of vertex-disjoint shortest augmenting paths extract karo; har ek ko augment karo.
Tab tak repeat karo jab tak BFS koi free right vertex na dhunde (no augmenting path → maximum, by Berge).

HopcroftKarp(L, R, adj):
    matchL = [None]*|L|;  matchR = [None]*|R|
    result = 0
    while BFS_builds_layers():        # phase: layered graph of shortest aug paths
        for u in L if matchL[u] is None:
            if DFS_augment(u):        # find vertex-disjoint shortest aug path
                result += 1
    return result
# BFS sets dist[] for free-left layer-by-layer; DFS only follows increasing layers

Worked example Tiny matching (two phases)

$L = {a, b}$ , $R = {x, y}$ , edges $a - x, a - y, b - x$ . Empty matching se shuru karo.

Phase 1 BFS: free lefts $a, b$ dist 0 par. Free rights $x, y$ tak edges se shortest augmenting length 1 milti hai. Layered graph mein sirf yeh length-1 paths hain.
Phase 1 DFS (maximal disjoint set of length-1 paths): $a \to x$ lo → match $a - x$ . Ab $b$ try karo: uska sirf ek neighbor $x$ is phase mein already use ho chuka hai, toh $b$ ke liye koi vertex-disjoint length-1 path nahi bachti. Why stop? Ek phase ke andar hum sirf shortest, vertex-disjoint paths use karte hain. Phase 1 deta hai +1. Current matching: ${a - x}$ .
Phase 2 BFS: sirf free left $b$ hai (aur free right $y$ ). Shortest augmenting path ab length 3 ki hai (matched edge $a - x$ se bounce karna padega): $b \to x$ (unmatched), $x \to a$ (matched edge), $a \to y$ (unmatched). Why length grew? Exactly Hopcroft–Karp guarantee: shortest augmenting length strictly increase hoti hai har phase mein.
Phase 2 DFS: $b - x - a - y$ along augment karo: edges flip karo → ab $b - x$ aur $a - y$ matched, $a - x$ freed. +1. Matching: ${b - x, a - y}$ .
Phase 3 BFS: koi free left vertex nahi bachta → stop. Result = 2 (perfect matching). ✅

Figure — Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp

5. König's Theorem (bonus jo answers derive karne deta hai)

Common mistakes

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek dance jisme ladke left par khade hain, ladkiyaan right par, aur ek hand-link sirf ladka↔ladki ke beech jaati hai, kabhi ladka↔ladka nahi. Yahi ek bipartite graph hai: do teams, links sirf across. Check karne ke liye, kisi ko red paint karo, unke saare doston ko blue, unke doston ko phir red — agar do dost kabhi same color pe aa jaayein, toh "do teams" plan fail ho jaata hai (doston ka ek odd loop hai). Matching har ladke ko ek ladki ke saath pair karna hai jisse koi double-booked na ho. Clever Hopcroft–Karp trick: har round mein yeh ek saath shortest non-overlapping "swap chains" ka ek bunch pakadta hai; chains round by round lambi hoti jaati hain, toh poori pairing super fast khatam hoti hai.

Connections

Graph Coloring — bipartite = 2-colorable special case (chromatic number $\leq 2$ ).
BFS / DFS — 2-coloring test aur phases ka engine.
Maximum Flow — bipartite matching max-flow mein reduce hoti hai (unit-capacity source→L→R→sink).
Berge's Theorem — augmenting-path optimality condition.
König's Theorem — matching ⟷ vertex cover ⟷ independent set duality.
Blossom Algorithm — general (non-bipartite) graphs mein matching.

Flashcards

Ek graph bipartite hai iff usmein koi ... nahi hai

odd-length cycle.

Edge (u,v) ke liye 2-coloring propagation rule

color[v] = 1 − color[u].

BFS/DFS 2-coloring bipartiteness test ki time complexity

O(V + E).

Matching ki definition

edges ka ek set jisme koi do vertices share nahi karte.

Augmenting path kya hota hai?

do unmatched vertices ke beech ek path jo unmatched/matched edges alternate karta hai (odd length, ek extra unmatched edge).

Berge's theorem

ek matching maximum hai iff usmein koi augmenting path nahi hai.

Augmenting path ke saath edges flip karne ka effect

matching size exactly 1 se badhti hai.

Hopcroft–Karp core idea

har phase BFS layering + DFS se shortest vertex-disjoint augmenting paths ka ek maximal set dhundta hai, phir sab augment karta hai.

Ek Hopcroft–Karp phase mein kaun se augmenting paths use hote hain?

sirf SHORTEST, vertex-disjoint augmenting paths ka ek maximal set; lambe/overlapping wale baad ke phases ke liye wait karte hain.

Hopcroft–Karp ki time complexity

O(E√V).

Hopcroft–Karp mein sirf O(√V) phases kyun hote hain?

shortest augmenting path length har phase mein strictly increase hoti hai, isliye √V phases ke baad sirf O(√V) augmentations bache rehte hain.

König's theorem (bipartite)

max matching size = min vertex cover size.

Bipartite graph mein max independent set matching ke terms mein

|V| − max matching size.

2-coloring test mein saare vertices par loop kyun karna padta hai?

disconnected components handle karne ke liye.

Hopcroft–Karp general graphs par kyun use nahi kar sakte?

odd cycles (blossoms) bipartite layered structure tod dete hain; Blossom algorithm use karo.