Matchings और augmenting paths
उद्देश्य और पूर्वज्ञान
Maximal, maximum और perfect matching का अंतर, exact matching size का प्रमाण, augmenting path से सुधार और cardinality तथा weight का अंतर सीखें। पूर्वज्ञान: finite simple undirected graph के terms और paths। यहाँ loops या parallel edges नहीं। ab और ba एक ही undirected edge हैं। Matching का size उसकी edges की संख्या है, covered vertices की नहीं।
1. Matching में चुनी edges endpoints साझा नहीं करतीं
Matching M⊆E में कोई दो edges एक vertex पर incident नहीं होतीं। M की किसी edge का endpoint हो तो vertex matched या covered, नहीं तो unmatched या exposed है। k edges की matching ठीक 2k vertices cover करती है, इसलिए n vertices पर size अधिकतम floor(n/2) है।
Path 1−2−3−4 में {12,34} matching है, लेकिन {12,23} नहीं: दोनों vertex 2 इस्तेमाल करती हैं। Matching का सभी vertices जोड़ना या एक connected subgraph बनाना जरूरी नहीं। वास्तव में चुनी edges आपस में अलग हैं। Matching को path, edge cover या vertex cover से न मिलाएँ।
Maximal matching में पुरानी सभी edges रखते हुए केवल एक और edge जोड़ना संभव नहीं। Maximum matching का size graph की सभी matchings में सबसे बड़ा होता है। उस size को ν(G) लिखें। Maximum global optimum है; maximal केवल सीधे एक edge और जोड़ने की असंभवता। हर maximum matching maximal है, उलटा जरूरी नहीं।
Perfect matching हर vertex cover करती है। इसमें n/2 edges हैं, इसलिए n even होना जरूरी। Perfect matching floor(n/2) bound तक पहुँचती है, इसलिए maximum है। Maximum matching का perfect होना जरूरी नहीं: triangle में हर matching अधिकतम एक edge की है।
2. हल किया उदाहरण: maximal, लेकिन maximum नहीं
छह vertices के path में edges {12,23,34,45,56} लें। M={23,45} हो। Unmatched vertices 1,6 हैं। हर बची edge किसी matched vertex को छूती है, इसलिए सीधे कोई edge और नहीं जोड़ सकते; M maximal है।
लेकिन M*={12,34,56} तीन-edge matching है। Upper bound floor(6/2)=3 से यह maximum सिद्ध है और perfect भी। इसलिए पहले की size-2 matching maximum नहीं थी। बड़ी matching पाने के लिए कुछ पुरानी edges हटानी पड़ सकती हैं; केवल दो exposed vertices के बीच unused edge खोजना पर्याप्त नहीं।
यही exact optimum सिद्ध करने का तरीका भी है: size-3 matching से lower bound ν≥3 और कोई matching 3 से बड़ी नहीं हो सकती, इससे upper bound ν≤3। केवल matching दिखाने से lower bound ही मिलता है।
3. Alternating और augmenting paths
Fixed matching M के सापेक्ष alternating path में edges बारी-बारी M के बाहर और भीतर होती हैं। Augmenting path ऐसा alternating simple path है जिसके दोनों endpoints unmatched हों। वह M के बाहर की edges से शुरू और समाप्त होता है, इसलिए बाहर की एक edge अधिक और कुल edges की संख्या odd होती है।
छह-vertex path में M={23,45} के लिए 1−2−3−4−5−6 augmenting path है। क्रम बाहर, भीतर, बाहर, भीतर, बाहर है। Membership पलटें: 23,45 हटाएँ और 12,34,56 जोड़ें। Size 2 से 3 हो जाता है।
परिणाम matching क्यों रहता है? हर internal path vertex अपनी पुरानी matching edge खोकर एक नई पाता है। पहले unmatched हर endpoint को एक edge मिलती है। Path के बाहर vertices की स्थिति नहीं बदलती। Augmenting path में k+1 outside और k inside edges हैं, इसलिए size ठीक 1 बढ़ता है।
हर alternating path augmenting नहीं। Endpoints वर्तमान matching के सापेक्ष unmatched होने चाहिए। Alternating cycle में inside और outside edges बराबर होती हैं; flip करने से उसी size की दूसरी matching मिल सकती है, बड़ी नहीं।
4. Augmenting path न मिलने का अर्थ
Berge theorem कहता है: matching maximum तभी और केवल तभी है जब उसके लिए augmenting path न हो। एक दिशा तुरंत स्पष्ट है: augmenting path बड़ी matching देता है, इसलिए वर्तमान matching maximum नहीं।
दूसरी दिशा के लिए M की तुलना उससे बड़ी matching N से करें। केवल उन edges को लें जो दोनों में से ठीक एक matching में हैं; यह symmetric difference M△N है। हर vertex पर अधिकतम एक M-edge और एक N-edge है। इसलिए इस subgraph के components alternating paths, alternating cycles या isolated vertices हैं।
Alternating cycles में दोनों matchings की edges बराबर होती हैं। कुल मिलाकर N में अधिक edges हैं तो किसी path component में N की एक edge अधिक होगी। वह N-edges से शुरू और समाप्त होगा तथा endpoints M में unmatched होंगे। इसलिए वह M का augmenting path है। इस प्रकार nonmaximum matching में augmenting path होना आवश्यक है।
यह theorem correctness का मानदंड है, यह दावा नहीं कि हर graph में naive path-search उतनी ही आसान है। Odd cycles, efficient general-graph matching algorithms को जटिल बनाती हैं। अगले पाठ में bipartite graphs हैं, जहाँ alternating-path search सरल है; blossom algorithms इस क्रम के वर्तमान implementation scope में नहीं।
5. उपयोगी bounds और graph families
Maximal matching size की factor-two guarantee देती है: M maximal और N maximum हो तो |N|≤2|M|। N की हर edge को M से covered किसी vertex को छूना होगा; नहीं तो वह M में जोड़ी जा सकती थी। N की edges endpoints साझा नहीं करतीं, इसलिए किसी एक M-edge के दो endpoints अधिकतम दो N-edges का हिसाब दे सकते हैं। इससे bound मिलता है।
यह tight हो सकता है। चार-vertex path में केवल middle edge size-1 maximal matching है, जबकि outer दो edges maximum size 2 देती हैं। यह guarantee size के लिए है, optimum होने या arbitrary edge weights के लिए नहीं।
Path Pₙ या cycle Cₙ (cycle में n≥3) पर adjacent disjoint pairs से floor(n/2) edges मिलती हैं और vertex-count bound maximum सिद्ध करता है। Complete graph Kₙ की matching number भी यही है। Star K₁,ₖ, k≥1, की matching number 1 है क्योंकि हर edge centre का उपयोग करती है।
इसलिए even vertices, connectedness और कोई isolated vertex न होना, तीनों मिलकर भी perfect matching की गारंटी नहीं देते। K₁,₃ में ये तीनों हैं, लेकिन maximum size 2 के बजाय 1 है। समस्या एक centre के लिए प्रतियोगिता है, किसी अलग leaf के neighbor न होने की नहीं।
6. Complete graph में perfect matchings गिनना
Labeled vertices वाले K₄ की perfect matching में दो edges हैं। Vertex 1 का partner बाकी 3 में से चुनें; बचा pair तय है। इसलिए 3 perfect matchings हैं, 6 नहीं। दो edges unordered set हैं; उनका लिखने का क्रम बदलने से नई matching नहीं।
K₆ में सबसे छोटे बचे label का partner चुनें: पहले 5 choices, फिर 3, फिर 1। Count 5·3·1=15। यह हर matching को edges का क्रम तय किए बिना uniquely बनाता है। सामान्यतः K₂ₖ में (2k−1)(2k−3)…1, या (2k)!/(2ᵏk!), perfect matchings हैं। Divisions हर pair का internal order और pairs का आपसी order हटाते हैं। Formula complete labeled graphs के लिए है; missing edges होने पर सीधे लागू नहीं।
7. Cardinality और weight अलग उद्देश्य हैं
चार-vertex path में w(12)=1,w(23)=10,w(34)=1 हों। Maximum-cardinality matching {12,34} में दो edges और total weight 2 है। {23} में एक edge, लेकिन weight 10 है, इसलिए weight वाला उद्देश्य उसे चुनता है। Augmenting path cardinality बढ़ाता है, weight बढ़ना जरूरी नहीं।
हमेशा बताएँ कि अधिकतम pairs चाहिए, अधिकतम total weight, या maximum-cardinality matchings में सबसे अच्छा weight। ये अलग optimization problems हैं। हमारे unweighted पाठ और प्रश्न cardinality लेते हैं, जब तक weights स्पष्ट न दिए हों।
हल की जाँच-सूची
चुनी edges मौजूद हों और endpoints साझा न करें। Covered vertices और edges अलग गिनें। Maximality के लिए देखें कि कोई edge दो exposed vertices जोड़ती है या नहीं। Maximum size के लिए augmenting paths या दिखाई matching से मेल खाता upper-bound certificate देखें। Perfectness में हर vertex जाँचें। इन अलग प्रश्नों की जगह “सबसे बड़ी दिखती है” जैसा अस्पष्ट दावा न रखें।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। Graphs finite, simple और undirected हैं; दिए matching, labeling और coloring conventions लागू रखें।
C01. Path 1−2−3−4−5−6 में M={23,45} का सही वर्गीकरण क्या है?
A. Matching नहीं B. Maximal, लेकिन maximum नहीं C. Maximum और perfect D. Maximum, लेकिन perfect नहीं
उत्तर: B
A: दोनों चुनी edges का कोई common endpoint नहीं, इसलिए matching है।
B: केवल 1 और 6 exposed हैं और adjacent नहीं, इसलिए edge जोड़ नहीं सकते। फिर भी {12,34,56} बड़ी matching है।
C: Vertices 1 और 6 uncovered हैं और size 3 की matching मिलती है। दोनों दावे गलत।
D: इसकी size 2 है, जबकि दिखाई गई तीन-edge matching upper bound 3 पाती है।
C02. Augmenting path में current matching की तीन edges हैं। उसमें बाहर की कितनी edges हैं और flip करने पर matching size कितनी बढ़ती है?
A. 3 बाहर; वृद्धि 0 B. 4 बाहर; वृद्धि 4 C. 6 बाहर; वृद्धि 3 D. 4 बाहर; वृद्धि 1
उत्तर: D
A: Augmenting path matching के बाहर शुरू और समाप्त होता है, इसलिए outside edges एक अधिक।
B: चार edges जुड़ती हैं, लेकिन तीन पुरानी हटती हैं; net gain चार नहीं।
C: दोनों exposed endpoints और alternation से चार outside edges, छह नहीं।
D: Alternating sequence में 3 inside और 4 outside edges; flip से वृद्धि 4−3=1।
C03. Labeled complete graph K₆ में कितनी अलग perfect matchings हैं?
A. 15 B. 6 C. 30 D. 720
उत्तर: A
A: एक fixed vertex का partner 5 तरीकों से और बचे चार को 3 तरीकों से pair करें: 5·3=15। या 6!/(2³·3!)।
B: Vertices की संख्या pair partitions नहीं गिनती; partner choices को जोड़ना नहीं, संयोजित करना है।
C: यह 15 edge sets को दो बार गिनता है; matching में pairs का क्रम नहीं होता।
D: 6! ordered vertex lists गिनता है। हर pair के अंदर और तीन pairs के बीच का क्रम हटाना होगा।
C04. Finite simple graph में matching M के लिए कोई augmenting path नहीं। कौन-सा निष्कर्ष निश्चित है?
A. M perfect है B. Graph bipartite है C. M maximum है D. M एकमात्र maximum matching है
उत्तर: C
A: Triangle की एक-edge matching का augmenting path नहीं, फिर भी एक vertex uncovered है।
B: वही triangle bipartite नहीं; criterion में bipartiteness आवश्यक नहीं।
C: Berge criterion: matching maximum तभी और केवल तभी है जब augmenting path न हो।
D: एक ही size की कई maximum matchings हो सकती हैं। Triangle की हर single edge maximum है।
C05. Star K₁,₃ के लिए कौन-सा कथन सही है?
A. चार vertices होने से maximum matching की size 2। B. Maximum matching की size 1 और perfect matching नहीं। C. Center की degree 3 होने से कोई matching नहीं। D. हर maximal matching खाली।
उत्तर: B
A: Even order केवल upper bound 2 देता है, अस्तित्व नहीं; star की कोई भी दो edges center साझा करती हैं।
B: एक edge संभव, दो असंभव क्योंकि सभी center पर मिलती हैं। दो leaves exposed रहती हैं।
C: Center की degree कुछ भी हो, कोई single edge valid matching है।
D: खाली matching में कोई edge जोड़ सकते हैं, इसलिए यहाँ maximal नहीं।
C06. चार-vertex path में edge weights w(12)=1,w(23)=10,w(34)=1 हैं। सही निष्कर्ष कौन-से हैं?
A. Maximum cardinality 10; maximum weight 2। B. Maximum-weight matching में दो edges होना आवश्यक। C. सभी maximal matchings का कुल weight समान। D. Maximum cardinality 2, लेकिन maximum-weight matching में weight 10 की एक edge।
उत्तर: D
A: Cardinality चुनी edges गिनती है, numerical edge weight नहीं।
B: दो-edge matching {12,34} का weight केवल 2, {23} के 10 से कम।
C: {23} और {12,34} दोनों maximal, लेकिन weights 10 और 2।
D: Outer edges से अधिकतम edge count 2। अकेली middle edge का weight 10, हर अन्य विकल्प से अधिक।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 के Discrete Mathematics में matching/colouring भाग विकसित करता है। Syllabus से प्रासंगिकता तय होती है, पूरे subject में mastery का दावा नहीं। MIT स्रोत graph definitions और theorems का संदर्भ हैं; यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। बाकी गहराई पाठ में स्पष्ट है, पूरी मान नहीं ली गई।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन