Bipartite matching: Hall की शर्त और vertex covers
उद्देश्य और पूर्वज्ञान
दिए side पर Hall theorem लगाना, bipartite graph में augmenting path खोजना और बराबर आकार के vertex cover से maximum matching सिद्ध करना सीखें। पूर्वज्ञान: matching, alternating/augmenting paths और finite sets। Graphs finite, simple, undirected हैं और bipartition L,R स्पष्ट है; हर edge L से R जाती है। Matching size हमेशा edges की संख्या है।
यह पाठ structural correctness और छोटे हाथ से किए searches विकसित करता है। सभी subsets की सूची बड़े graph का efficient algorithm होने का दावा नहीं, और bipartite search अपने आप general-graph blossom algorithm नहीं बनती।
1. एक side cover करना हमेशा perfect नहीं
Matching, L को cover करती है यदि हर left vertex, R के अलग neighbor से matched हो। इसके लिए |L|≤|R| जरूरी है, लेकिन side sizes अलग होने पर भी छोटे side को cover कर सकते हैं। Perfect matching दोनों sides cover करती है; इसलिए bipartite graph में |L|=|R| जरूरी।
केवल equal sizes पर्याप्त नहीं। L={a,b,c},R={1,2,3}, edges {a1,b1,c2,c3} लें। दोनों sides size 3 हैं और हर vertex का neighbor है। फिर भी a,b दोनों को vertex 1 चाहिए; दोनों matched नहीं हो सकते। Size-2 matching {a1,c2} मौजूद है, लेकिन size 3 नहीं।
यह सामूहिक बाधा है: हर vertex अलग जाँचने से subset के भीतर प्रतियोगिता छूटती है। पूरे subset के distinct available neighbors गिनने चाहिए; degrees जोड़कर साझा neighbors दो बार नहीं गिनें।
2. Hall theorem और शर्त की आवश्यकता
S⊆L के लिए N(S)={r∈R: किसी s∈S से r adjacent है}। Neighborhood set है; कई edges से पहुँचा neighbor एक ही बार गिना जाता है।
Hall theorem: L-covering matching तभी और केवल तभी मौजूद है जब हर S⊆L के लिए |N(S)|≥|S|। Empty subset में 0≥0 स्वतः सही। L-covering matching न होने को सिद्ध करने के लिए कम neighbors वाला एक subset पर्याप्त। Hall से existence सिद्ध करने के लिए हर subset की शर्त सही चाहिए: छोटे graph में enumeration या एक सामान्य तर्क से।
Necessity किसी proposed matching से दिखती है: S के vertices को अलग matched neighbors चाहिए, जो सभी N(S) में होंगे। इसलिए कम-से-कम |S| neighbors चाहिए। ऊपर S={a,b} पर N(S)={1}; 1<2 असंभवता का certificate है। लेकिन N(L)={1,2,3} का size 3 है; केवल पूरा left side जाँचने से इस graph को गलत ढंग से पास कर देंगे।
Sufficiency Hall theorem की शक्तिशाली दिशा है: ऐसी हर बाधा न होने पर matching सचमुच मौजूद है; केवल आसान local समस्या न दिखने का दावा नहीं।
3. Unequal sides का सकारात्मक worked example
L={a,b,c},R={1,2,3,4} और edges {a1,a2,b2,b3,c1,c3,c4} लें। Singleton neighborhoods के sizes 2,2,3 हैं। Pairs के लिए N({a,b})={1,2,3}, N({a,c})={1,2,3,4}, N({b,c})={1,2,3,4}। अंत में N(L)=R का size 4 है।
हर nonempty subset Hall bound पूरा करता है; empty भी। Concrete matching {a2,b3,c4}, L को 3 edges से cover करती है। |L|=3 से इससे बड़ी matching नहीं; यह maximum है। Perfect नहीं, क्योंकि right vertex 1 unmatched है। Hall के निष्कर्ष में कौन-सा side cover हुआ, यह बताएँ; चुपचाप perfectness न जोड़ें।
Edge counting से उपयोगी theorem मिलता है। d≥1 वाले finite d-regular bipartite graph में d|L|=d|R|, इसलिए sides equal हैं। S⊆L से ठीक d|S| edges निकलती हैं और N(S) में अधिकतम d|N(S)| पहुँच सकती हैं। इसलिए |S|≤|N(S)| और Hall से perfect matching। d≥1 जरूरी है: isolated vertices वाला edgeless graph 0-regular है, लेकिन vertices मौजूद हों तो perfect matching नहीं।
4. Alternating search की directions
Matching M दी हो तो सभी unmatched left vertices से शुरू करें। M के बाहर की edges left से right और भीतर की edges right से left जाएँ। किसी unmatched right vertex पर पहुँचने से augmenting path मिलता है। Directions alternation लागू करती हैं; matching information के बिना सामान्य reachability पर्याप्त नहीं।
उदाहरण: L={a,b,c},R={1,2,3}, edges {a1,a2,b1,c2,c3} और M={a1,c2}। Unmatched left b, unmatched right 3 है। b→1 (outside), 1→a (inside), a→2 (outside), 2→c (inside), c→3 (outside) जाएँ। Flip करने से {b1,a2,c3} size-3 perfect matching मिलती है।
“b को अभी free direct neighbor दे दें” वाली कोशिश रुक जाएगी, क्योंकि b का एकमात्र neighbor 1 occupied है। Alternating path पुराने assignments को बदलकर जरूरी क्षमता देती है, बिना पुराने vertices को unmatched छोड़े।
हर augmentation size ठीक 1 बढ़ाती है, इसलिए केवल सीमित augmentations संभव। सभी unmatched left vertices से search करके भी unmatched right न मिले तो augmenting path नहीं और matching maximum है। हर search में traversal हर vertex/edge को सीमित बार देख सकती है, लेकिन यहाँ correctness का प्रमाण complexity formula याद करने पर निर्भर नहीं।
5. Vertex covers से upper bound
Vertex cover C⊆V हर edge को छूता है: हर uv∈E के लिए कम-से-कम u या v, C में हो। Minimum vertex cover सबसे कम vertices लेता है। यह matching से अलग है, जो edges चुनती है, और edge cover से भी, जो vertices छूने के लिए edges चुनता है।
हर matching का size हर vertex cover के size से अधिक नहीं। हर matching edge को cover vertex चाहिए और अलग matching edges के endpoints अलग हैं, इसलिए अलग cover vertices चाहिए। अतः k-edge matching और k-vertex cover एक-दूसरे की optimality सिद्ध करते हैं, theorem का नाम लिए बिना भी।
Obstruction graph {a1,b1,c2,c3} में M={a1,c2} size 2 है। Vertex set {1,c} चारों edges छूता है, इसलिए size-2 cover है। Matching-cover inequality से ν=2 और minimum cover size τ=2। Size-1 cover नहीं हो सकता, क्योंकि एक vertex दोनों disjoint matching edges को नहीं छू सकता।
Kőnig theorem: हर finite bipartite graph में ν(G)=τ(G)। इसका अर्थ sets समान होना नहीं: एक में edges, दूसरे में vertices। यह हर nonbipartite graph के लिए सही नहीं। Triangle में maximum matching size 1, minimum vertex cover size 2 है।
6. Maximum matching से minimum cover बनाएँ
M maximum हो। सभी unmatched left vertices से directed alternating search करें। L में पहुँचे vertices Z_L और R में Z_R हों। तब
C=(L\Z_L) ∪ Z_R
minimum vertex cover है।
हर edge cover क्यों? मानें lr में l∈Z_L और r∉Z_R, जिससे दोनों endpoints चुने न जाते। lr, M के बाहर हो तो l से search, r तक पहुँचती, विरोधाभास। lr भीतर हो तो reached matched left vertex अपने matching edge से r के रास्ते पहुँचा था; unmatched starting vertex की ऐसी edge नहीं। फिर भी r reached होगा। इसलिए कोई edge uncovered नहीं।
|C|=|M| क्यों? कोई unmatched right reached नहीं, नहीं तो augmenting path होता। हर unmatched left starting vertex है और C में नहीं आता। हर matched edge के या तो दोनों endpoints reached हैं या कोई नहीं। पहले मामले में C उसका right endpoint चुनता है, दूसरे में left endpoint। इसलिए हर matching edge के लिए ठीक एक चुना vertex; |C|=|M| और optimality सिद्ध।
Obstruction graph में M={a1,c2} हो तो केवल unmatched left b है। Search b,1,a तक पहुँचती है। इसलिए Z_L={a,b},Z_R={1}, और C={c,1}, वही direct certificate।
जाँच-सूची और दायरा
L,R बताएँ। N(S) में अलग neighbors गिनें, edges नहीं। Hall की all-subsets शर्त और एक-subset counterexample अलग रखें। Side-covering और perfectness अलग। Hand search में सही direction के outside/inside edges बारी-बारी लें। Optimality के लिए matching और उतने आकार का cover दें या augmenting path न होना सिद्ध करें। Weighted assignment, stable matching और arbitrary-graph vertex-cover algorithms अलग समस्याएँ हैं; वे यहाँ पूरे नहीं हुए।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। Graphs finite, simple और undirected हैं; दिए matching, labeling और coloring conventions लागू रखें।
C01. L={a,b,c}, R={1,2,3}, E={a1,b1,c2,c3} में L को saturate करने के लिए कौन-सा set Hall condition का उल्लंघन दिखाता है?
A. S={c}, क्योंकि |N(S)|=2 B. S=L, क्योंकि |N(S)|=3 C. S={a,b}, क्योंकि |N(S)|=1 D. S=∅, क्योंकि |N(S)|=0
उत्तर: C
A: यहाँ 2≥1, इसलिए इस subset के लिए condition सही।
B: यहाँ 3≥3; केवल पूरी left side जाँचने से बाधा छूटती है।
C: दो left vertices का एकमात्र neighbor 1 है: |N(S)|=1<2=|S|।
D: Empty subset 0≥0 पूरा करता है; यह violating witness नहीं।
C02. उन्हीं दो तीन-vertex parts पर E={a1,b1,c2,c3} में maximum matching size ν और minimum vertex-cover size τ क्या हैं?
A. ν=2, τ=2 B. ν=3, τ=3 C. ν=1, τ=2 D. ν=2, τ=3
उत्तर: A
A: Matching {a1,c2} की size 2 और cover {1,c} हर edge छूता है। ν≤τ से बराबर certificates दोनों optima सिद्ध करते हैं।
B: Hall का violating subset तीन-edge matching रोकता है और दो-vertex cover से τ=3 गलत।
C: Disjoint edges a1 और c2 पहले ही size 2 की matching देते हैं।
D: Cover {1,c} की size 2, इसलिए minimum cover में 3 आवश्यक नहीं।
C03. Bipartite graph में |L|=3, |R|=4 और पूरे L को saturate करती matching है। क्या निष्कर्ष निकलता है?
A. पूरे graph में matching perfect है। B. Matching में चार edges हैं। C. एक vertex exposed होने से बड़ी matching अवश्य है। D. Matching size 3 की maximum है, लेकिन पूरे graph में perfect नहीं।
उत्तर: D
A: Parts के unequal sizes होने से right side का एक vertex exposed रहता है।
B: हर matching edge अलग left vertex लेती है; केवल तीन उपलब्ध हैं।
C: अकेला exposed vertex पर्याप्त नहीं; हर matching edge को अलग left endpoint चाहिए।
D: तीन left vertices saturate करने वाली तीन edges smaller-part upper bound पाती हैं। चार right vertices में ठीक एक unmatched।
C04. दिए d≥1 assumption में finite d-regular bipartite graphs के लिए कौन-सा कथन सही है?
A. Left vertices हमेशा right से अधिक। B. Parts बराबर आकार के हैं और perfect matching है। C. d odd होने पर perfect matching नहीं। D. यह निष्कर्ष arbitrary part sizes वाले हर d=0 graph में भी सही।
उत्तर: B
A: Edges गिनने से d|L|=d|R|; d>0 होने पर cancel करके बराबर sizes।
B: S⊆L की d|S| incident edges N(S) में जाती हैं, जिसकी कुल क्षमता अधिकतम d|N(S)|। Hall सही और बराबर parts से saturation perfect।
C: Proof हर positive d के लिए है। Degree 1 graphs तो disjoint matching edges ही हैं।
D: d=0 में isolated vertices की perfect matching आवश्यक नहीं और parts बराबर भी आवश्यक नहीं। d से भाग देना गलत होगा।
C05. E={a1,a2,b1,c2,c3}, M={a1,c2} में augmenting path b−1−a−2−c−3 flip करें। कौन-सी matching मिलती है?
A. {a1,c2,b1} B. {a1,c2,c3} C. {b1,a2,c3} D. {a2,c2}
उत्तर: C
A: a1 और b1 vertex 1 साझा करते हैं; केवल पहली edge जोड़ने से matching नहीं बनती।
B: c2 और c3, c साझा करते हैं; path की पुरानी matching edges हटानी होंगी।
C: a1,c2 हटाएँ और b1,a2,c3 जोड़ें। सभी छह vertices ठीक एक बार covered और size 2 से 3।
D: a2 तथा c2 दोनों right vertex 2 लेते हैं, इसलिए matching नहीं।
C06. कौन-सा उदाहरण दिखाता है कि ν=τ equality हर simple graph के लिए नहीं कह सकते?
A. Triangle में ν=1 और τ=2। B. Single edge में ν=τ=1। C. Edgeless graph में ν=τ=0। D. चार-vertex path में ν=τ=2।
उत्तर: A
A: Triangle की कोई भी दो edges मिलती हैं, इसलिए ν=1। एक vertex opposite edge छोड़ता है, दो सभी cover करते हैं, इसलिए τ=2। Graph bipartite नहीं।
B: यह bipartite उदाहरण equality पूरा करता है, counterexample नहीं।
C: दोनों quantities शून्य हैं, इसलिए equality सही है, गलत नहीं।
D: दो-edge matching और दो-vertex cover से इस bipartite path में equality सिद्ध होती है।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 के Discrete Mathematics में matching/colouring भाग विकसित करता है। Syllabus से प्रासंगिकता तय होती है, पूरे subject में mastery का दावा नहीं। MIT स्रोत graph definitions और theorems का संदर्भ हैं; यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। बाकी गहराई पाठ में स्पष्ट है, पूरी मान नहीं ली गई।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन