Matching — bipartite graph, Hall-এর উপপাদ্য আর stable matching

১ · Matching কী — maximal, maximum আর perfect

এই পর্বে graph মানে সসীম undirected simple graph G = (V, E), যদি না অন্য কিছু বলা থাকে। Vertex v-এর প্রতিবেশী-সেট N(v); একটি সেট X-এর জন্য N(X) মানে X-এর অন্তত একজনের প্রতিবেশী এমন সব vertex. সংজ্ঞাগুলোর বিস্তারিত পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ।

নিচের ছবিটি একটি bipartite graph: vertex দুই দলে ভাগ, বাঁয়ে L (রাইডার a, b, c, d), ডানে R (অর্ডার 1, 2, 3, 4), আর প্রতিটি edge দুই দলের মধ্যে। মোটা সবুজ রেখা একটি matching M = {a–1, c–2, d–3}.

এই M-এ আর কোনো edge যোগ করা যায় না: b-এর একমাত্র প্রতিবেশী 1 আগেই ব্যস্ত, আর 4-এর একমাত্র প্রতিবেশী d-ও ব্যস্ত। তাই M maximal. অথচ {b–1, a–2, c–3, d–4} চারটি edge-এর একটি perfect matching, তাই M maximum নয়। “লোভী” পদ্ধতি (যেকোনো খালি edge নিয়ে যাওয়া) ঠিক এমন maximal matching-এ আটকে যায়। তবু এর একটি নিশ্চয়তা আছে।

1. M*-এর প্রতিটি edge e-এর অন্তত একটি প্রান্ত M-এ saturated; নইলে e-কে M-এ যোগ করা যেত। — maximal-এর সংজ্ঞা
2. প্রতিটি e ∈ M*-এর জন্য এমন একটি প্রান্ত বেছে নিন। M* matching বলে আলাদা edge-এর বাছাই করা প্রান্ত আলাদা। — matching-এ প্রান্ত ভাগ হয় না
3. বাছাই করা সব প্রান্ত M-এর edge-গুলোর 2|M|টি প্রান্তের মধ্যে, তাই |M*| ≤ 2|M|. ∎ — পর্ব ৩২-এর গণনা

সীমাটি নিখুঁত: চার vertex-এর path 1–2–3–4-এ শুধু মাঝের edge {2–3} একটি maximal matching (আকার 1), অথচ {1–2, 3–4} আকার 2. দুটি সহজ গণনাও মনে রাখুন। Complete graph K_2n-এ perfect matching (2n − 1)(2n − 3)⋯3·1টি: vertex 1-এর সঙ্গী বাছার 2n − 1 উপায়, তারপর বাকি সবচেয়ে ছোট vertex-এর 2n − 3 উপায়, এভাবে (পর্ব ৩১-এর গুণের নিয়ম)। আর K_n,n-এ perfect matching মানে L থেকে R-এ একটি bijection, তাই n!টি। Perfect matching থাকতে vertex-সংখ্যা জোড় হতেই হবে, তবে তা যথেষ্ট নয়।

২ · Augmenting path আর Berge-এর উপপাদ্য

ছবির M থেকে perfect matching-এ কীভাবে যাওয়া যায়? b থেকে শুরু করে পালা করে “M-এর বাইরের edge, M-এর edge” ধরে হাঁটুন: b–1 (বাইরে), 1–a (M-এ), a–2 (বাইরে), 2–c (M-এ), c–3 (বাইরে), 3–d (M-এ), d–4 (বাইরে)। দুই প্রান্ত b আর 4 দুজনেই free. এখন এই পথের প্রতিটি edge-এর অবস্থা উল্টে দিন: M-এর তিনটি edge বাদ, বাইরের চারটি ঢুকে যায়। Matching এক বড় হয়।

“উল্টে দেওয়া” কাজটির গাণিতিক নাম symmetric difference: A ⊕ B = (A − B) ∪ (B − A), অর্থাৎ ঠিক একটিতে আছে এমন উপাদান (পর্ব ১৫)। P-কে তার edge-সেট ধরলে নতুন matching M ⊕ P.

1M = {a–1, c–2, d–3}2b থেকে: b–1, তারপর 1–a3a থেকে: a–2, তারপর 2–c4c থেকে: c–3, তারপর 3–d5d থেকে: d–4, 4 free!6M ← M ⊕ P

(⇒ দিক, contrapositive) ধরুন P একটি M-augmenting path, যার k + 1টি edge M-এর বাইরে আর kটি M-এ।

1. M ⊕ P-তে P-এর ভেতরের প্রতিটি vertex ঠিক একটি edge পায়: আগে তার M-edge ছিল P-তে, এখন P-এর অন্য edge-টি। — পালা করে আসা edge
2. P-এর দুই প্রান্ত আগে free ছিল, এখন ঠিক একটি edge পায়; P-এর বাইরের vertex-এর কিছুই বদলায় না। তাই M ⊕ P একটি matching. — প্রান্ত free
3. |M ⊕ P| = |M| − k + (k + 1) = |M| + 1, তাই M maximum নয়। — গণনা

(⇐ দিক, contrapositive) ধরুন M maximum নয়: একটি matching M* আছে যার |M*| > |M|.

1. H = M ⊕ M* নিন (edge-সেট, সঙ্গে সব vertex). প্রতিটি vertex M-এর বড়জোর একটি আর M*-এর বড়জোর একটি edge ছোঁয়, তাই H-এ প্রতিটি degree ≤ 2. — দুটিই matching
2. যে graph-এর সব degree ≤ 2, তার প্রতিটি component একটি path বা একটি cycle (একা vertex-ও দৈর্ঘ্য ০-এর path). H-এ একই vertex-এ মেলা দুটি edge একই matching-এর হতে পারে না, তাই প্রতিটি path ও cycle-এ M আর M*-এর edge পালা করে আসে। — degree ≤ 2-এর গঠন
3. পালা করে আসায় প্রতিটি cycle-এর দৈর্ঘ্য জোড়, আর তাতে M আর M*-এর edge সমান। H-এ M*-এর edge বেশি (|M* − M| > |M − M*|, কারণ সাধারণ অংশ দুই দিক থেকেই বাদ), তাই কোনো একটি path-এ M*-এর edge M-এর চেয়ে বেশি: ঠিক একটি বেশি, আর তার প্রথম ও শেষ edge M*-এর। — pigeonhole
4. সেই path-এর একটি প্রান্ত u নিন। u যদি M-এ saturated হতো একটি edge f দিয়ে, তবে f ∉ M* (u-এর M*-edge তো H-এ আছে, তাই M-এ নেই), ফলে f ∈ H, আর H-এ deg(u) = 2 হতো; কিন্তু u প্রান্ত, তার degree 1. তাই u M-free, অন্য প্রান্তও তাই। — বিরোধ
5. অতএব path-টি একটি M-augmenting path. ∎

উপপাদ্যটি একটি algorithm-এর নকশা দেয়: খালি matching থেকে শুরু করুন, augmenting path পেলে উল্টে দিন, আর না পাওয়া পর্যন্ত চালিয়ে যান। প্রতিবার আকার ১ বাড়ে, তাই বড়জোর |V|/2 বার। কঠিন অংশ হলো দ্রুত augmenting path খোঁজা; bipartite graph-এ তা সরল DFS (§৪-এর কোড), সাধারণ graph-এ odd cycle সমস্যা বাধায় (§৮)।

৩ · Hall-এর বিয়ের উপপাদ্য — কখন সবাই জোড়া পায়

বাজারঘরের গুদামে পাঁচজন কর্মী আর পাঁচটি শিফট। কে কোন শিফট করতে পারেন, তালিকা আছে। প্রত্যেককে আলাদা একটি শিফট দেওয়া কি সম্ভব? প্রতিটি সম্ভাব্য ভাগ (5! = 120টি) পরীক্ষা করা যায়, কিন্তু ৫০ জন হলে 50! অসম্ভব। Hall-এর উপপাদ্য বলে, উত্তর “না” হলে তার একটি ছোট, যাচাইযোগ্য কারণ সবসময় থাকে।

একটি স্পষ্ট বাধা: যদি তিনজন কর্মী মিলে মাত্র দুটি শিফট করতে পারেন, তবে তিনজনকে আলাদা শিফট দেওয়া অসম্ভব (pigeonhole). তাই প্রয়োজনীয় শর্ত: L-এর প্রতিটি উপসেট X-এর জন্য |N(X)| ≥ |X|. বিস্ময়কর কথা হলো, শর্তটি যথেষ্টও।

(⇒) সহজ: matching X-এর প্রতিটি সদস্যকে N(X)-এর আলাদা একজন সঙ্গী দেয়, তাই |N(X)| ≥ |X|. (⇐) দিকের প্রমাণ |L|-এর ওপর strong induction দিয়ে (Halmos আর Vaughan-এর ধাঁচ বলে পরিচিত)।

1. ভিত্তি |L| = 1: L = {u}, শর্ত অনুযায়ী |N(u)| ≥ 1, তাই u-এর একটি প্রতিবেশী v আছে; {u–v} কাজ করে। — base case
2. ধরুন |L| ≥ 2, আর |L|-এর চেয়ে ছোট L-ওয়ালা সব bipartite graph-এ দাবি সত্য। দুটি ক্ষেত্র। — inductive hypothesis
3. ক্ষেত্র ক: প্রতিটি অশূন্য X ⊊ L-এ |N(X)| ≥ |X| + 1 (শর্তে এক “বাড়তি”)। যেকোনো u ∈ L আর তার একটি প্রতিবেশী v নিন; G′ = G − u − v. G′-এ যেকোনো অশূন্য X ⊆ L − {u}-এর প্রতিবেশী বড়জোর একজন (v) কমেছে: |N′(X)| ≥ |X| + 1 − 1 = |X|. Hypothesis অনুযায়ী G′-এ L − {u} saturate করা matching আছে; তাতে u–v যোগ করুন। — বাড়তি একজন খরচ করা
4. ক্ষেত্র খ: কোনো অশূন্য X₀ ⊊ L-এ |N(X₀)| = |X₀| (শর্ত ঠিক টায়-টায়)। G₁ = X₀ ∪ N(X₀)-এর ওপর induced subgraph. X ⊆ X₀-এর প্রতিবেশী সবাই N(X₀)-এ, তাই G₁-এ Hall-এর শর্ত বহাল; |X₀| < |L| বলে hypothesis X₀ saturate করা matching M₁ দেয়। — টাইট দলকে আলাদা করে মেলানো
5. G₂ = (L − X₀) ∪ (R − N(X₀))-এর ওপর induced subgraph. যেকোনো Y ⊆ L − X₀-এর G₂-তে প্রতিবেশী N₂(Y) = N(Y) − N(X₀), আর N(Y ∪ X₀) হলো N₂(Y) আর N(X₀)-এর disjoint union. তাই |N₂(Y)| = |N(Y ∪ X₀)| − |X₀| ≥ |Y| + |X₀| − |X₀| = |Y|. — G-তে Y ∪ X₀-এর জন্য শর্ত
6. |L − X₀| < |L|, তাই hypothesis G₂-তে matching M₂ দেয়। M₁ আর M₂-এর vertex আলাদা, তাই M₁ ∪ M₂ একটি matching যা পুরো L saturate করে। ∎ — জোড়া লাগানো

ক্ষেত্র খ-এর কৌশলটি লক্ষ করুন: যে দলের শর্ত “টায়-টায়”, তাদের প্রতিবেশীদের তাদের জন্যই রেখে দিতে হয়, নইলে তারা জায়গা পায় না। “বিয়ের উপপাদ্য” নামটি এসেছে পাত্র-পাত্রীর পছন্দ-তালিকার পুরোনো রূপ থেকে। আরেকটি পুরোনো রূপ system of distinct representatives: সেটের একটি পরিবার A₁, …, A_n থেকে প্রতিটি সেটের জন্য আলাদা একটি প্রতিনিধি বাছা যায় ঠিক তখন, যখন যেকোনো kটি সেটের union-এ অন্তত kটি উপাদান।

উপপাদ্যটির ব্যবহারিক মূল্য হলো certificate বা প্রমাণপত্র: matching না থাকলে একটি X দেখালেই চলে যার |N(X)| < |X|; যে কেউ তা এক নজরে যাচাই করতে পারেন। নিচের stepper কর্মী–শিফট তালিকায় সেই X খোঁজে।

1A:{1,2} B:{2} C:{1,2} D:{3,4,5} E:{4}2|X| = 1: প্রত্যেকের N3|X| = 2: ১০টি জোড়া4|X| = 3: X = {A, B, C}5ফল: ν = 4, cover, সমাধান

নিচের ব্লকটি ঠিক এই কাজ করে: ছোট থেকে বড় সব X পরীক্ষা করে প্রথম ভাঙা X ফেরত দেয়। তারপর ৫০০টি এলোমেলো bipartite graph-এ মেলায় যে Hall-এর শর্ত মানা আর brute force-এর উত্তর একই। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
from itertools import combinations, permutations
def hall_violation(adj):                 # smallest X with |N(X)| < |X|
    L = sorted(adj)
    for k in range(1, len(L) + 1):
        for X in combinations(L, k):
            N = set().union(*(adj[x] for x in X))
            if len(N) < k:
                return X, sorted(N)
    return None
def saturates_L(adj, R):                 # brute force: try every injection
    L = sorted(adj)
    return any(all(r in adj[u] for u, r in zip(L, p))
               for p in permutations(R, len(L)))
staff = {"A": {1, 2}, "B": {2}, "C": {1, 2}, "D": {3, 4, 5}, "E": {4}}
print("staff-shift:", hall_violation(staff))
staff["C"].add(3)                        # C can also take shift 3
print("after C learns shift 3:", hall_violation(staff))
random.seed(35); agree = with_pm = 0
for trial in range(500):
    nL, nR = random.randint(1, 5), random.randint(1, 6)
    R = list(range(nR))
    adj = {u: {r for r in R if random.random() < 0.35} for u in range(nL)}
    hall_ok = hall_violation(adj) is None
    assert hall_ok == (nL <= nR and saturates_L(adj, R))
    agree += 1; with_pm += hall_ok
print(agree, "random graphs: Hall's condition <=> L-saturating matching;",
      with_pm, "had one")

staff-shift: (('A', 'B', 'C'), [1, 2])
after C learns shift 3: None
500 random graphs: Hall's condition <=> L-saturating matching; 204 had one

৪ · König-এর উপপাদ্য — matching আর vertex cover একই সংখ্যা

বাজারঘর প্রতিটি সম্ভাব্য রাইডার–অর্ডার জোড়া পর্যবেক্ষণ করতে চায়, কিন্তু খরচ বাঁচাতে যত কম সম্ভব মানুষ বা অর্ডারে নজরদার বসাবে, যাতে প্রতিটি edge-এর অন্তত এক প্রান্তে নজরদার থাকে। এই সেটের নাম vertex cover: এমন vertex-সেট C, যা প্রতিটি edge-এর অন্তত একটি প্রান্ত ধারণ করে। সবচেয়ে ছোট cover-এর আকার τ(G) (গ্রিক “টাউ”)।

সহজ দিক যেকোনো graph-এ: ν(G) ≤ τ(G). কারণ maximum matching-এর প্রতিটি edge ঢাকতে cover-এর একটি vertex লাগে, আর matching-এর edge প্রান্ত ভাগ করে না বলে একই vertex দুটি edge ঢাকে না। ত্রিভুজে ν = 1 কিন্তু τ = 2, তাই সাধারণ graph-এ সমতা নাও থাকতে পারে। Bipartite graph-এ থাকে।

প্রমাণ (augmenting path দিয়ে, নির্মাণসহ): M একটি maximum matching, U = L-এর M-free vertex-গুলো। Z = যেসব vertex U থেকে কোনো M-alternating path দিয়ে পৌঁছানো যায় (U নিজেও Z-এ), Z_L = Z ∩ L, Z_R = Z ∩ R. সংজ্ঞা দিন C = (L − Z_L) ∪ Z_R.

1. U থেকে alternating path L থেকে R-এ যায় M-এর বাইরের edge দিয়ে, আর R থেকে L-এ ফেরে M-এর edge দিয়ে। Z_R-এর প্রতিটি vertex M-এ saturated: নইলে সেই alternating path একটি augmenting path হতো, যা Berge-এর উপপাদ্য অনুযায়ী অসম্ভব। আর তার M-সঙ্গী Z_L-এ। — উপপাদ্য ২.২
2. C প্রতিটি edge uv (u ∈ L, v ∈ R) ঢাকে: u ∉ Z_L হলে u ∈ C. u ∈ Z_L আর uv ∉ M হলে u পর্যন্ত alternating path-এর শেষে uv যোগ করলে v-তে পৌঁছানো যায়, তাই v ∈ Z_R ⊆ C. u ∈ Z_L আর uv ∈ M হলে u free নয়, তাই u-তে পৌঁছানো হয়েছে তার সঙ্গী v থেকেই, ফলে v ∈ Z_R. — cover-এর শর্ত
3. C-এর প্রতিটি vertex saturated: L − Z_L-এ কোনো free vertex নেই (free-রা সবাই U ⊆ Z_L), আর Z_R-এর জন্য ধাপ ১. — সংজ্ঞা
4. M-এর কোনো edge-এর দুই প্রান্তই C-তে নেই: uv ∈ M আর v ∈ Z_R হলে ধাপ ১ অনুযায়ী u ∈ Z_L, তাই u ∉ C. ফলে C-এর প্রতিটি vertex-কে তার M-edge-এ পাঠানোর নিয়মটি one-to-one, আর |C| ≤ |M|. — injection
5. C একটি cover, তাই |C| ≥ τ(G) ≥ ν(G) = |M|. মিলিয়ে |C| = |M|, অর্থাৎ τ(G) = ν(G). ∎

প্রমাণটি দুটি জিনিস একসঙ্গে দেয়: একটি matching আর সমান আকারের একটি cover. দুটি হাতে পেলে যে কেউ সহজে নিশ্চিত হতে পারেন যে দুটিই সর্বোত্তম, কারণ ν ≤ τ সবসময় সত্য। এটিই “duality”-র ধরন, যা পর্ব ৫৯ Connectivity-এর Menger-এর উপপাদ্যেও দেখেছেন। Hall-এর উপপাদ্যও König থেকে আসে: L saturate করা matching না থাকলে |C| = ν < |L|, আর X = L − C নিলে N(X) ⊆ C ∩ R (C cover), তাই |N(X)| ≤ |C| − |C ∩ L| < |L| − |C ∩ L| = |X|.

নিচের ব্লক augmenting-path (DFS) পদ্ধতিতে maximum matching বের করে, প্রমাণের Z থেকে cover বানায়, আর ২০০টি এলোমেলো bipartite graph-এ তিনটি সংখ্যা মেলায়: algorithm-এর matching, brute force-এর ν, আর cover-এর আকার। Cover সত্যিই প্রতিটি edge ঢাকে কি না, তাও পরীক্ষা হয়।

import random
from itertools import combinations
def max_matching(L, adj):               # augmenting paths (DFS)
    mate = {}                            # right vertex -> left vertex
    def augment(u, seen):
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                if v not in mate or augment(mate[v], seen):
                    mate[v] = u; return True
        return False
    for u in L: augment(u, set())
    return mate
def konig_cover(L, adj, mate):          # alternating reach from free left
    zL = {u for u in L if u not in mate.values()}; zR = set(); todo = list(zL)
    while todo:
        for v in adj[todo.pop()]:
            if v not in zR:
                zR.add(v)
                if mate[v] not in zL: zL.add(mate[v]); todo.append(mate[v])
    return (set(L) - zL) | zR
def brute_nu(E, top):                    # largest k with k disjoint edges
    return next(k for k in range(top, -1, -1) if any(
        len({x for e in S for x in e}) == 2 * k for S in combinations(E, k)))
random.seed(64); ok = 0
for trial in range(200):
    L = [f"L{i}" for i in range(random.randint(1, 5))]
    R = [f"R{j}" for j in range(random.randint(1, 5))]
    adj = {u: [v for v in R if random.random() < 0.4] for u in L}
    E = [(u, v) for u in L for v in adj[u]]
    mate = max_matching(L, adj); C = konig_cover(L, adj, mate)
    assert len(mate) == brute_nu(E, min(len(L), len(R))) == len(C)
    assert all(u in C or v in C for u, v in E); ok += 1
print(ok, "random bipartite graphs: augmenting = brute force = |cover|")

200 random bipartite graphs: augmenting = brute force = |cover|

৫ · Dilworth-এর উপপাদ্যের প্রমাণ — König থেকে

পর্ব ৫৬-এ Dilworth-এর উপপাদ্য প্রমাণ ছাড়া বলা হয়েছিল: সসীম poset-এর width w (সবচেয়ে বড় antichain-এর আকার) হলে উপাদানগুলো ঠিক wটি chain-এ ভাগ করা যায়, এর কম chain-এ নয়। “কম নয়” অংশ সহজ ছিল। এখন বাকি অংশ, D. R. Fulkerson-এর ১৯৫৬ সালের ধারণা বলে পরিচিত পথে।

নির্মাণ: |P| = n. প্রতিটি x ∈ P-এর দুটি কপি নিন: বাঁয়ে x⁻, ডানে x⁺. Bipartite graph B-তে x⁻–y⁺ edge থাকবে ঠিক যখন x ≺ y (x ≼ y আর x ≠ y). x⁻–y⁺ edge মানে “কোনো chain-এ x-এর ঠিক পরে y বসতে পারে”।

1. Matching থেকে chain: B-এর একটি matching M নিন, আর প্রতিটি x⁻–y⁺ ∈ M-কে “x → y” তীর ধরুন। প্রতিটি x-এর বড়জোর একটি পরের তীর (x⁻ একবার) আর বড়জোর একটি আগের তীর (x⁺ একবার)। তীর সবসময় কঠোরভাবে ওপরে যায়, তাই কোনো চক্র হয় না: তীরগুলো P-কে কয়েকটি শৃঙ্খলে ভাগ করে, আর transitivity অনুযায়ী প্রতিটি শৃঙ্খল একটি chain. kটি উপাদানের chain-এ k − 1টি তীর, তাই chain-এর সংখ্যা n − |M|. — প্রতিটি তীর দুটি টুকরো জোড়ে
2. ফলে maximum matching দিয়ে n − ν(B)টি chain-এ ভাগ পাওয়া যায়। — ধাপ ১, M maximum
3. Cover থেকে antichain: König অনুযায়ী B-এর একটি vertex cover C আছে যার |C| = ν(B). A = {x ∈ P : x⁻ ∉ C আর x⁺ ∉ C} নিন। C-এর প্রতিটি vertex বড়জোর একটি x-কে বাদ দেয়, তাই |A| ≥ n − |C| = n − ν(B). — উপপাদ্য ৪.১
4. A একটি antichain: x, y ∈ A আর x ≺ y হলে x⁻–y⁺ একটি edge, যার কোনো প্রান্ত C-তে নেই, অথচ C cover. বিরোধ। — cover-এর সংজ্ঞা
5. তাই width ≥ |A| ≥ n − ν(B) = (ধাপ ২-এর chain-সংখ্যা) ≥ সবচেয়ে কম chain-সংখ্যা ≥ width, শেষটি সহজ দিক। সব অসমতা সমতা। ∎

হাতে একটি ছোট উদাহরণ: 12-এর উৎপাদক {1, 2, 3, 4, 6, 12}, সম্পর্ক “ভাগ করে” (∣)। Matching 1→2, 2→4, 4→12, 3→6 (আকার 4) দুটি chain দেয়: 1 ∣ 2 ∣ 4 ∣ 12 আর 3 ∣ 6. Antichain {4, 6} (4 ∤ 6, 6 ∤ 4). দুই সংখ্যাই 2, তাই width = 2 (scratch-এ সব উপসেট পরীক্ষা করে মেলানো)। নিচের ব্লক একই কাজ 60-এর ১২টি উৎপাদকে করে, যেখানে পর্ব ৫৬ চারটি chain দেখিয়েছিল।

from itertools import combinations
X = [d for d in range(1, 61) if 60 % d == 0]          # poset: divisors, a | b
up = {x: [y for y in X if y != x and y % x == 0] for x in X}   # x- -> y+
nxt = {}                                              # matching: x- matched to y+
def augment(x, seen):
    for y in up[x]:
        if y not in seen:
            seen.add(y)
            owner = next((a for a in nxt if nxt[a] == y), None)
            if owner is None or augment(owner, seen):
                nxt[x] = y; return True
    return False
for x in X: augment(x, set())
starts = [x for x in X if x not in nxt.values()]      # nobody points to x
chains = []
for s in starts:
    c = [s]
    while c[-1] in nxt: c.append(nxt[c[-1]])
    chains.append(c)
print("matching size", len(nxt), "-> chains", len(X) - len(nxt), chains)
zL = {x for x in X if x not in nxt}; zR = set(); todo = list(zL)  # Konig
while todo:
    for y in up[todo.pop()]:
        if y not in zR:
            zR.add(y)
            owner = next(a for a in nxt if nxt[a] == y)
            if owner not in zL: zL.add(owner); todo.append(owner)
cover = {("-", x) for x in X if x not in zL} | {("+", y) for y in zR}
anti = [x for x in X if ("-", x) not in cover and ("+", x) not in cover]
print("cover size", len(cover), "-> antichain", anti)
assert all(a % b and b % a for a, b in combinations(anti, 2))
print("width = min number of chains =", len(anti))

matching size 8 -> chains 4 [[1, 2, 4, 12, 60], [3, 6, 30], [5, 10, 20], [15]]
cover size 8 -> antichain [4, 6, 10, 15]
width = min number of chains = 4

৬ · Regular bipartite graph আর ওজনসহ assignment

বাজারঘর ঠিক করেছে, প্রতিটি রাইডার ঠিক তিনটি এলাকায় কাজ জানবেন আর প্রতিটি এলাকা ঠিক তিনজন রাইডার জানবেন। এমন ব্যবস্থায় কি প্রতিদিন প্রত্যেক রাইডারকে আলাদা একটি এলাকা দেওয়া যায়? Hall-এর উপপাদ্য এক লাইনে উত্তর দেয়। (k-regular মানে প্রতিটি vertex-এর degree ঠিক k.)

1. Edge গুনুন দুইভাবে: প্রতিটি edge-এর ঠিক একটি প্রান্ত L-এ, তাই |E| = k|L|; একইভাবে |E| = k|R|. তাই |L| = |R|. — পর্ব ৩৭-এর double counting
2. যেকোনো X ⊆ L নিন। X থেকে বের হওয়া edge ঠিক k|X|টি, আর সবাই N(X)-এ পড়ে। N(X)-এর প্রতিটি vertex মোট kটি edge পায়, তাই এই edge-গুলো বড়জোর k|N(X)|টি। ফলে k|X| ≤ k|N(X)|, অর্থাৎ |N(X)| ≥ |X|. — double counting
3. Hall অনুযায়ী L saturate করা matching আছে; |L| = |R| বলে এটি perfect. — উপপাদ্য ৩.১
4. এই matching সরালে graph (k − 1)-regular bipartite থাকে; k-এর ওপর induction-এ kটি perfect matching পাওয়া যায়। ∎ — পর্ব ১০-এর induction

শেষ অংশটি König-এর ১৯১৬ সালের একটি ফলের সঙ্গে যুক্ত বলে উল্লেখ করা হয়: bipartite graph-এর edge-গুলো Δ রঙে (Δ = সর্বোচ্চ degree) রাঙানো যায়, যাতে একই vertex-এ দুটি edge একই রঙ না পায়। রাইডারের উদাহরণে অর্থ: তিন দিনের একটি পালা বানানো যায়, যাতে প্রতিদিন প্রত্যেকে আলাদা এলাকায় যান আর তিন দিনে নিজের তিনটি এলাকাই ঘোরা হয়। Graph coloring-এর বিস্তারিত পর্ব ৬৩ “Graph coloring — chromatic number, scheduling আর চার রঙের উপপাদ্য”-এ।

ওজনসহ matching: assignment problem আর Hungarian পদ্ধতির ধারণা

এবার প্রতিটি রাইডার–অর্ডার জোড়ার একটি খরচ আছে (মিনিটে যাতায়াত সময়, সংখ্যাগুলো কাল্পনিক)। মোট খরচ সবচেয়ে কম রেখে একটি perfect matching চাই: এর নাম assignment problem. n জনের জন্য n!টি সম্ভাবনা, তাই brute force দ্রুত অচল। Hungarian পদ্ধতি (Harold Kuhn, ১৯৫৫; König আর Egerváry-র কাজের ওপর ভিত্তি করে, তাই এই নাম) polynomial সময়ে সমাধান দেয়। এর মূল ধারণা একটি “নিম্নসীমার প্রমাণপত্র”:

• প্রতিটি রাইডার i-কে একটি সংখ্যা u_i আর প্রতিটি অর্ডার j-কে v_j দিন, যাতে সব জোড়ায় u_i + v_j ≤ c_ij (c_ij = খরচ)।
• তাহলে যেকোনো perfect matching-এর খরচ ≥ ∑u_i + ∑v_j, কারণ প্রতিটি i আর প্রতিটি j ঠিক একবার আসে।
• যেখানে সমতা u_i + v_j = c_ij, সেই “টাইট” edge-গুলো দিয়ে perfect matching পাওয়া গেলে সেটিই সর্বোত্তম। না পেলে König-এর cover বলে দেয় কোন u, v কতটা বদলালে নতুন টাইট edge আসে; পদ্ধতিটি তা বারবার করে।

উদাহরণ: তিন রাইডার, তিন অর্ডার, খরচ-matrix-এর সারি (9, 2, 7), (6, 4, 3), (5, 8, 1). প্রতিটি সারির সবচেয়ে ছোট সংখ্যা u = (2, 3, 1); বাদ দিলে প্রতিটি কলামের সবচেয়ে ছোট বাকি v = (3, 0, 0). টাইট ঘর: (১, ২), (২, ১), (২, ৩), (৩, ৩). এদের মধ্যে perfect matching: রাইডার ১ → অর্ডার ২, ২ → ১, ৩ → ৩, খরচ 2 + 6 + 1 = 9. নিম্নসীমা ∑u + ∑v = 6 + 3 = 9. দুই সংখ্যা সমান, তাই 9-ই সর্বনিম্ন, আর কোনো ৬টি assignment গোনা লাগেনি (scratch-এ ৬টিই গুনে মেলানো: পরের সেরাটি 10). এই “দুই দিকের প্রমাণপত্র” হলো linear programming duality-র একটি রূপ। Algorithm-এর পূর্ণ কোড DSA কোর্সের পর্ব ৪৭-এ।

৭ · Stable matching — Gale–Shapley-এর প্রস্তাব আর প্রত্যাখ্যান

বাজারঘরের চারজন শিক্ষানবিশ A, B, C, D চারটি গুদামে (গাজীপুর G, নারায়ণগঞ্জ N, সাভার S, টঙ্গী T) প্রশিক্ষণ নেবেন। প্রত্যেক শিক্ষানবিশের গুদামের একটি পছন্দ-তালিকা আছে, আর প্রতিটি গুদামেরও শিক্ষানবিশদের একটি তালিকা। এবার শুধু “সবাই জোড়া পেল” যথেষ্ট নয়; বিপদ হলো এমন একটি জোড়া, যারা দুজনেই বর্তমান সঙ্গীর চেয়ে একে অন্যকে বেশি চান। তারা নিয়ম ভেঙে নিজেরা চুক্তি করে ফেলবেন।

Gale–Shapley algorithm (David Gale আর Lloyd Shapley, ১৯৬২; “deferred acceptance” নামেও পরিচিত): যতক্ষণ কোনো প্রস্তাবদাতা p একা আছেন, p তাঁর তালিকার পরের গ্রহীতা w-কে প্রস্তাব দেন, যাঁকে আগে দেননি। w একা হলে প্রস্তাবটি “ধরে রাখেন”; কাউকে ধরে রাখলে দুজনের মধ্যে যাঁকে বেশি পছন্দ তাঁকে রাখেন, অন্যজনকে ফিরিয়ে দেন, আর ফেরত পাওয়া জন আবার একা। কেউ একা না থাকলে ধরে রাখা জোড়াগুলোই উত্তর। নিচে সব একা প্রস্তাবদাতা একসঙ্গে প্রস্তাব দেন, রাউন্ডে রাউন্ডে।

1A: T S N G   G: A C D B2B: G N T S   N: B C D A3C: T G S N   S: C D B A4D: G S N T   T: B D A C5রাউন্ড ১6রাউন্ড ২7রাউন্ড ৩8stability যাচাই

1. থামা: প্রত্যেক প্রস্তাবদাতা একজন গ্রহীতাকে বড়জোর একবার প্রস্তাব দেন, তাই মোট প্রস্তাব ≤ n · n. প্রতিটি ধাপে একটি প্রস্তাব হয়, তাই algorithm থামে। — সসীম গণনা
2. গ্রহীতার দিক: একবার প্রস্তাব পেলে w সবসময় কাউকে ধরে রাখেন, আর ধরে রাখা জন শুধু তাঁর তালিকায় ওপরে ওঠেন। — নিয়ম থেকে, ধাপে ধাপে induction
3. সবাই জোড়া পান: ধরুন শেষে p একা। তাহলে p সব nজনকে প্রস্তাব দিয়ে ফেরত পেয়েছেন, তাই ধাপ ২ অনুযায়ী nজন গ্রহীতাই কাউকে ধরে রাখছেন, আর তাঁরা সবাই p নন: n − 1 জন প্রস্তাবদাতা nজনের হাতে, যা অসম্ভব (pigeonhole). — বিরোধ
4. Stable: ধরুন (p, w) blocking: p তাঁর সঙ্গী M(p)-এর চেয়ে w-কে বেশি চান। p তালিকা ধরে নিচে নামেন, তাই M(p)-এর আগে w-কে প্রস্তাব দিয়েছিলেন, আর কোনো এক সময় w তাঁকে ফেরত দিয়েছেন বা নেননি, কারণ তখন হাতে p-এর চেয়ে পছন্দের কেউ ছিলেন। ধাপ ২ অনুযায়ী w-এর শেষ সঙ্গী M(w) তাঁর কাছে অন্তত তত ভালো, তাই w, p-এর চেয়ে M(w)-কে বেশি চান। এটি blocking-এর বিরোধী। ∎ — বিরোধ

1. দাবি: কোনো প্রস্তাবদাতা কখনো একজন সম্ভব সঙ্গীর কাছ থেকে প্রত্যাখ্যাত হন না। বিপরীতে, এমন প্রথম ঘটনাটি নিন: w, p-কে ফেরাল p′-এর জন্য, যেখানে w p-এর সম্ভব সঙ্গী, অর্থাৎ কোনো stable S-এ S(p) = w. — সময়ে প্রথম ঘটনা, well-ordering
2. w-এর কাছে p′ > p. আর p′ তালিকা ধরে নামতে নামতে w-তে পৌঁছেছেন, তাই w-এর আগের সবাই তাঁকে ফিরিয়েছেন; এটি প্রথম “সম্ভব-প্রত্যাখ্যান” বলে তাঁদের কেউ p′-এর সম্ভব সঙ্গী নন। S(p′) p′-এর একজন সম্ভব সঙ্গী আর S(p′) ≠ w, তাই p′ তালিকায় w-কে S(p′)-এর চেয়ে ওপরে রাখেন। — ধাপে ধাপে নামা
3. তাহলে S-এ (p′, w) blocking: p′ নিজের S-সঙ্গীর চেয়ে w চান, আর w নিজের S-সঙ্গী p-এর চেয়ে p′ চান। কিন্তু S stable, বিরোধ। — সংজ্ঞা ৭.১
4. তাই প্রত্যেক p তাঁর সব সম্ভব সঙ্গীর ওপরের কারও কাছ থেকেই ফেরত পান, আর ফল (যা stable, তাই p-এর সঙ্গী সম্ভব) ঠিক সেরা সম্ভব সঙ্গী। এই বর্ণনা প্রস্তাবের ক্রমের ওপর নির্ভর করে না। ∎

উল্টো দিকটিও জানা যায় (McVitie আর Wilson, ১৯৭১ বলে উল্লেখ করা হয়): একই matching-এ প্রত্যেক গ্রহীতা পান তাঁর সবচেয়ে অপছন্দের সম্ভব সঙ্গী। তাই কে প্রস্তাব দেয়, সেই নকশা-সিদ্ধান্তের ফল বাস্তবে বড়। নিচের ব্লক উদাহরণটি পুরো যাচাই করে।

from itertools import permutations
P = {"A": "TSNG", "B": "GNTS", "C": "TGSN", "D": "GSNT"}   # trainees' lists
W = {"G": "ACDB", "N": "BCDA", "S": "CDBA", "T": "BDAC"}   # warehouses' lists
def gale_shapley(P, W):
    nxt = {p: 0 for p in P}; held = {}; free = sorted(P); proposals = 0
    while free:
        p = free.pop(0); w = P[p][nxt[p]]; nxt[p] += 1; proposals += 1
        if w not in held:
            held[w] = p
        elif W[w].index(p) < W[w].index(held[w]):       # w trades up
            free.append(held[w]); held[w] = p
        else:
            free.append(p)                              # w rejects p
    return {p: w for w, p in held.items()}, proposals
def blocking_pairs(M, P, W):
    owner = {w: p for p, w in M.items()}
    return [(p, w) for p in P for w in W
            if P[p].index(w) < P[p].index(M[p])
            and W[w].index(p) < W[w].index(owner[w])]
M, k = gale_shapley(P, W)
print("trainees propose:", dict(sorted(M.items())), "proposals:", k)
print("blocking pairs:", blocking_pairs(M, P, W))
stable = [dict(zip(P, perm)) for perm in permutations(W)
          if not blocking_pairs(dict(zip(P, perm)), P, W)]
print("stable among all 24:", [''.join(s.values()) for s in stable])
for p in P:                                  # proposer-optimal check
    assert all(P[p].index(M[p]) <= P[p].index(s[p]) for s in stable)
R, _ = gale_shapley(W, P)
print("warehouses propose:", dict(sorted((p, w) for w, p in R.items())))

trainees propose: {'A': 'T', 'B': 'N', 'C': 'G', 'D': 'S'} proposals: 7
blocking pairs: []
stable among all 24: ['GNST', 'TNGS']
warehouses propose: {'A': 'G', 'B': 'N', 'C': 'S', 'D': 'T'}

৮ · সাধারণ graph-এ matching — odd cycle, Tutte আর Edmonds

Berge-এর উপপাদ্য যেকোনো graph-এ সত্য, কিন্তু Hall আর König শুধু bipartite graph-এ। সাধারণ graph-এ বাধা আসে odd cycle থেকে: ত্রিভুজে প্রতিটি vertex-এর প্রতিবেশী দুজন, তবু perfect matching নেই (vertex বিজোড়), আর ν = 1 < 2 = τ. Bipartite হওয়া মানেই odd cycle না থাকা (পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”), আর এই কারণেই সেখানে সব এত পরিষ্কার।

প্রয়োজনীয়তার দিকটি সহজ: G − S-এর প্রতিটি বিজোড় component-এর অন্তত একটি vertex-কে বাইরে, অর্থাৎ S-এ, সঙ্গী খুঁজতে হয়, আর S-এর প্রতিটি vertex একজনকেই নিতে পারে। উদাহরণ: তারকা K_1,3-এ (একটি কেন্দ্র, তিনটি পাতা) S = {কেন্দ্র} সরালে তিনটি একা vertex, তিনটি বিজোড় component > 1 = |S|, তাই perfect matching নেই। যথেষ্টতার প্রমাণ দীর্ঘতর, তাই এখানে বাদ। একটি পরিচিত ফল (Petersen, ১৮৯১ বলে উল্লেখ করা হয়): প্রতিটি 3-regular graph যাতে কোনো bridge নেই, তাতে perfect matching আছে; Petersen graph-এ এমন matching ঠিক ৬টি (scratch-এ গুনে মেলানো)।

Algorithm-এর দিকে সমস্যাটি এমন: alternating path খুঁজতে গিয়ে একটি odd cycle-এ ঘুরে এলে একই vertex-এ “জোড়” আর “বিজোড়” দুই অবস্থায় পৌঁছানো যায়, আর সরল DFS ভুল পথে আটকে যায়। Jack Edmonds ১৯৬৫ সালে দেখান, এমন odd cycle (তাঁর ভাষায় “blossom” বা ফুল) পেলে সেটিকে একটি vertex-এ সংকুচিত করে খোঁজ চালিয়ে যাওয়া যায়, আর augmenting path পেলে ফুল খুলে আসল path বের করা যায়। এই blossom algorithm সাধারণ graph-এ maximum matching polynomial সময়ে দেয়। ওজনসহ সাধারণ matching-এরও polynomial সমাধান আছে, Edmonds-এরই আরেকটি কাজ বলে উল্লেখ করা হয়। তুলনায়, একটি 3-uniform hypergraph-এ (প্রতিটি “edge” তিনটি vertex জোড়ে) perfect matching আছে কি না, সেই প্রশ্ন NP-complete; DSA কোর্সের পর্ব ৬৪ দেখুন।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: Maximal বনাম maximum

৬ vertex-এর path P₆: 0–1–2–3–4–5. (ক) ν কত? (খ) সবচেয়ে ছোট maximal matching কত বড়? (গ) উপপাদ্য ১.২-এর সীমা মেলে কি?

1. (ক) {0–1, 2–3, 4–5} perfect, তাই ν = 3.
2. (খ) {1–2, 3–4}: বাকি edge 0–1, 2–3, 4–5-এর প্রত্যেকটির একটি প্রান্ত ব্যস্ত, তাই maximal; আকার 2. একটি edge বড়জোর ৩টি edge ছোঁয়, তাই একটিতে ৫টি edge আটকানো যায় না।
3. (গ) 3 ≤ 2 · 2, মেলে (scratch-এ সব edge-সেট পরীক্ষা করে মেলানো)।

অঙ্ক ২: Perfect matching গোনা

K₆-এ আর K_3,3-এ কয়টি perfect matching? উত্তর: K₆-এ 5 · 3 · 1 = 15 (§১-এর যুক্তি), K_3,3-এ 3! = 6 (L থেকে R-এ bijection). দুটিই scratch-এ প্রতিটি matching গুনে মেলানো।

অঙ্ক ৩: König দিয়ে প্রমাণপত্র

§৩-এর কর্মী–শিফট graph-এ দেখান যে ৪-এর বেশি কর্মী একসঙ্গে কাজ পাবেন না, Hall ব্যবহার না করে। উত্তর: {1, 2, D, 4} একটি vertex cover (A, B, C-এর সব edge 1 বা 2-এ, D-এর সব edge D-তে, E–4 ঢাকে 4), আকার 4. ν ≤ τ, তাই ν ≤ 4; আর A–1, B–2, D–3, E–4 আকার 4-এর matching, তাই ν = 4.

প্রমাণের ভুল ধরুন: “লোভী matching-ই maximum”

একজন লিখলেন: “লোভী পদ্ধতি একটি maximal matching M দেয়। ধরুন M*-এ আরও বেশি edge আছে। তাহলে M*-এর একটি edge e আছে যা M-এ নেই। e-কে M-এ যোগ করলে বড় matching হয়, যা M-এর maximal হওয়ার বিরোধী। তাই M maximum.”

ভুল কোথায়: “e ∉ M” থেকে “M ∪ {e} একটি matching” আসে না; e-এর একটি প্রান্ত M-এর অন্য কোনো edge-এ ব্যস্ত থাকতে পারে, আর maximal-এর সংজ্ঞা ঠিক সেটাই বলে। পাল্টা-উদাহরণ: path 1–2–3–4-এ M = {2–3} maximal, অথচ M* = {1–2, 3–4} বড়, আর M*-এর কোনো edge M-এ যোগ করা যায় না। সঠিক কথা উপপাদ্য ১.২ (|M| ≥ ν/2) আর Berge: M থেকে M*-এ যেতে edge “যোগ” নয়, একটি augmenting path ধরে “বদল” লাগে, এখানে 1–2–3–4 নিজেই।

১০ · AI-এর যুগে — matching-এর প্রমাণ আর হিসাব যাচাই

Matching-এর প্রশ্নে AI সহকারী নাম আর সংজ্ঞা সাধারণত ঠিক বলে, কিন্তু শর্ত বাদ দেয়, দুই দিক গুলিয়ে ফেলে, আর হাতের হিসাবে ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Graph-এর ধরন স্পষ্ট, আর bipartite-নির্ভর উপপাদ্য শুধু bipartite graph-এ লাগানো হয়েছে
• “যদি এবং কেবল যদি”-র দুই দিকই আলাদাভাবে প্রমাণিত, converse গুলিয়ে যায়নি
• Induction থাকলে তা যেকোনো বড় graph থেকে শুরু হয়ে ছোটটিতে নেমেছে
• ছোট graph-এ brute force দিয়ে ν, τ বা matching-এর সংখ্যা মিলিয়েছি
• Stable matching-এর দাবিতে সব জোড়া ধরে blocking pair খুঁজেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Matching-এর উত্তরের সঙ্গে প্রমাণপত্রও চাইবেন: matching, cover, ভাঙা X বা blocking pair-এর তালিকা, যা কয়েক লাইনের কোডে মেলানো যায়।