ग्राफ सिद्धांत — संबद्धता, मेल व रंगन

ग्राफ के प्रश्न ऐसे दिखते हैं कि उन्हें चित्र चाहिए और प्रायः उन्हें सर्वसमिका चाहिए। पहले पकड़ने योग्य वह हस्तमिलन प्रमेयिका है: सभी कोटियों का योग कोरों की संख्या का दुगुना होता है, अतः कोटि-योग सदा सम है और विषम-कोटि शीर्षों की संख्या सदा सम। वह एक सम-विषमता का तथ्य किसी रचना के बिना “क्या ऐसा ग्राफ विद्यमान है” प्रश्नों का पूरा परिवार तय कर देता है — पाँच शीर्ष प्रत्येक कोटि तीन वाले ग्राफ का कोटि-योग 15 होता, जो विषम है, अतः वह विद्यमान नहीं हो सकता। तीन और सर्वसमिकाएँ शेष अधिकांश काम करती हैं। n शीर्षों पर वृक्ष के ठीक n − 1 कोर होते हैं और किन्हीं दो शीर्षों के बीच अद्वितीय पथ, अतः n − 1 से अधिक कोरों वाले संबद्ध ग्राफ में चक्र होना ही चाहिए और कम वाला संबद्ध ही नहीं हो सकता। पूर्ण ग्राफ Kₙ के n(n − 1)/2 कोर होते हैं। और आयलर सूत्र v − e + f = 2 बिना प्रतिच्छेदन खींचे किसी भी संबद्ध समतलीय ग्राफ हेतु सत्य है, और इसी से समतलीयता के प्रश्न अंकगणित बन जाते हैं। दोनों नामित प्रकरणों पर: ग्राफ द्विभाजित ठीक तब है जब उसमें विषम चक्र न हो, जो उसे हाथ से दो-रंगने के प्रयास से बहुत सरल है; और उसकी रंगन-संख्या नीचे से उसके सबसे बड़े गुच्छ के आकार से और ऊपर से Δ + 1 से परिबद्ध है, जहाँ χ(Kₙ) = n, χ(सम चक्र) = 2 व χ(विषम चक्र) = 3। मेल का एक परिणाम नाम से जानने योग्य है — कोनिग प्रमेय, कि द्विभाजित ग्राफ में सबसे बड़े मेल व सबसे छोटे शीर्ष-आवरण का आकार समान होता है — क्योंकि वह उस प्रश्न को, जिसका उत्तर आपको नहीं दिखता, ऐसे प्रश्न में बदल देता है जिसका दिखता है। अंततः आयलर-पथ की शर्तें फिर शुद्ध सम-विषमता हैं: संबद्ध ग्राफ में बंद आयलर परिपथ ठीक तब है जब प्रत्येक कोटि सम हो, और खुला आयलर पथ ठीक तब जब ठीक दो कोटियाँ विषम हों।

गणना-सर्वसमिकाएँ

पाँच सर्वसमिकाएँ, व प्रत्येक जिस प्रश्न का उत्तर देती है
सर्वसमिकावह क्या तय करती है
Σ deg(v) = 2|E|सम-विषमता से अस्तित्व। कोटि 3 के पाँच शीर्ष कोटि-योग 15 देते हैं — विषम, अतः ऐसा ग्राफ नहीं। विषम-कोटि शीर्षों की संख्या सदा सम होती है।
n शीर्षों पर वृक्ष के n − 1 कोर होते हैंचक्र व संबद्धता। संबद्ध ग्राफ में n − 1 से अधिक कोर चक्र पर विवश करते हैं; n − 1 से कम संबद्धता असंभव कर देते हैं।
|E(Kₙ)| = n(n − 1)/2ऊर्ध्व परिबंध। K₅ के 10 कोर हैं; n शीर्षों पर किसी भी सरल ग्राफ के अधिकतम उतने ही।
n शीर्षों पर k-नियमित ग्राफ के nk/2 कोर होते हैंअस्तित्व व गणना दोनों। 6 शीर्षों पर 3-नियमित ग्राफ के 9 कोर हैं; 5 शीर्षों पर वह विद्यमान नहीं हो सकता, क्योंकि nk विषम है।
v − e + f = 2 (संबद्ध समतलीय)फलक व समतलीयता। सपाट खींचे K₄ हेतु v = 4, e = 6, अतः f = 4। K₅ व K₃,₃ दो न्यूनतम असमतलीय ग्राफ हैं।
🧠 केली: nⁿ⁻² लेबल-युक्त वृक्ष
n शीर्षों पर भिन्न लेबल-युक्त वृक्षों की संख्या n(n−2) है — चार शीर्षों पर 16, पाँच पर 125। घातांक गलत होना सरल है, अतः उसे उस सबसे छोटी स्थिति पर टिकाएँ जिसे आप हाथ से जाँच सकें: तीन शीर्षों पर सूत्र 3¹ = 3 देता है, और {a, b, c} पर वास्तव में तीन लेबल-युक्त वृक्ष हैं, मध्य शीर्ष के प्रत्येक चुनाव हेतु एक। ध्यान दें गिनती किसकी है: लेबल-युक्त वृक्षों की, जहाँ शीर्ष विभेद्य हैं। लेबल-रहित वृक्ष-आकारों की संख्या भिन्न व बहुत छोटी अनुक्रम है, और "लेबल-युक्त" कहने वाला प्रश्न बता रहा है कि उसे कौन चाहिए।

रंगन, व विषम-चक्र परीक्षण

  • ग्राफ द्विभाजित ठीक तब है जब उसमें कोई विषम चक्र न हो। चलाने योग्य परीक्षण यही है — विषम चक्र खोजना दो-रंगन का प्रयास कर पीछे हटने से बहुत तेज़ है। प्रत्येक वृक्ष द्विभाजित है, क्योंकि वृक्ष में चक्र ही नहीं होते।
  • χ(Kₙ) = n, क्योंकि प्रत्येक शीर्ष-युग्म संलग्न है और कोई दो एक रंग साझा नहीं कर सकते। सामान्यतः χ(G) सबसे बड़े गुच्छ के आकार से कम नहीं, और पहले पकड़ने योग्य अधो परिबंध यही है।
  • χ(चक्र) सम चक्र हेतु 2 और विषम हेतु 3 है। C₆ को दो रंग चाहिए, C₅ को तीन, और उछाल उसी कारण होती है जिससे द्विभाजनीयता विफल होती है: विषम चक्र में घूमने पर दो संलग्न शीर्षों को सहमत होना पड़ता है।
  • प्रत्येक समतलीय ग्राफ 4-रंगनीय है, और प्रत्येक ग्राफ (Δ + 1)-रंगनीय, जहाँ Δ सबसे बड़ी कोटि है। दोनों ऊर्ध्व परिबंध हैं, और ठीक रंगन-संख्या पूछने वाला प्रश्न प्रायः नीचे से गुच्छ-परिबंध और ऊपर से इनमें एक चाहता है, जो एक ही मान पर मिलें।
🎯 कोनिग: द्विभाजित ग्राफ में मेल व आवरण एक ही संख्या हैं
मेल कोरों का ऐसा समुच्चय है जिनमें कोई दो शीर्ष साझा न करें; शीर्ष-आवरण शीर्षों का ऐसा समुच्चय जो प्रत्येक कोर को स्पर्श करे। किसी भी ग्राफ में सबसे बड़ा मेल सबसे छोटे आवरण से अधिक नहीं, क्योंकि प्रत्येक मेलित कोर को अपना आवरण-शीर्ष चाहिए। कोनिग प्रमेय कहता है कि द्विभाजित ग्राफ में दोनों बराबर हैं — जो दोनों दिशाओं में उपयोगी है: आकार k का मेल व आकार k का आवरण दिखा दें, और आपने आगे खोजे बिना दोनों को इष्टतम सिद्ध कर दिया। कोरों {(1,4), (1,5), (2,5), (3,6)} वाले द्विभाजित ग्राफ हेतु सबसे बड़ा मेल {(1,4), (2,5), (3,6)} है, आकार 3, अतः सबसे छोटा शीर्ष-आवरण भी आकार 3 का है। सामान्य ग्राफों हेतु यह समता असत्य है — विषम चक्र उसे तोड़ देता है — इसीलिए मेल के प्रश्न में "द्विभाजित" शब्द वास्तविक काम कर रहा है।

आयलर पथ — फिर सम-विषमता

संबद्ध ग्राफ हेतु: बंद आयलर परिपथ ठीक तब विद्यमान है जब प्रत्येक शीर्ष की कोटि सम हो, और खुला आयलर पथ ठीक तब जब ठीक दो शीर्षों की कोटि विषम हो — वे दो ही सिरे होते हैं। तीसरी स्थिति नहीं है, क्योंकि विषम-कोटि शीर्षों की संख्या सदा सम होती है। अतः किसी भी आयलर-प्रश्न का उत्तर कोटि-गणना है, और कोनिग्सबर्ग के पुल इसलिए विफल हैं कि उसके चारों शीर्ष विषम हैं।

⚠️ आयलर कोरों की बात है, हैमिल्टन शीर्षों की
आयलर पथ प्रत्येक कोर एक बार प्रयोग करता है; हैमिल्टन चक्र प्रत्येक शीर्ष एक बार देखता है। दोनों एक ही समस्या के रूप नहीं हैं: आयलर के पास ऊपर की स्वच्छ सम-विषमता कसौटी है और वह रैखिक समय में निर्णेय है, जबकि हैमिल्टनीयता हेतु ऐसी कोई कसौटी ज्ञात नहीं और उसका निर्णय NP-पूर्ण है। हैमिल्टन चक्र के अस्तित्व का कारण कोटि-सम-विषमता का तर्क देने वाला प्रश्न संभवतः सही उत्तर हेतु गलत कारण दे रहा है, और यहाँ मानक भ्रामक विकल्प वही है।

मुख्य बिंदु

  • Σ deg(v) = 2|E|, अतः कोटि-योग सम है और विषम-कोटि शीर्षों की संख्या सम। कोटि 3 के पाँच शीर्ष विद्यमान नहीं हो सकते।
  • n शीर्षों पर वृक्ष के n − 1 कोर होते हैं। संबद्ध ग्राफ में उससे अधिक चक्र पर विवश करते हैं; कम संबद्धता असंभव करते हैं।
  • केली: n शीर्षों पर nⁿ⁻² लेबल-युक्त वृक्ष — चार पर 16, पाँच पर 125। घातांक को n = 3 पर टिकाएँ, जहाँ उत्तर 3 है।
  • द्विभाजित ठीक तब जब कोई विषम चक्र न हो — दो-रंगन का प्रयास करने के बजाय चक्र हेतु परीक्षण करें।
  • χ(Kₙ) = n, χ(सम चक्र) = 2, χ(विषम चक्र) = 3। गुच्छ-आकार χ को नीचे से और Δ + 1 ऊपर से परिबद्ध करता है।
  • कोनिग: द्विभाजित ग्राफ में सबसे बड़ा मेल सबसे छोटे शीर्ष-आवरण के बराबर है। सामान्य ग्राफों हेतु यह समता विफल है।
  • आयलर परिपथ हेतु सभी कोटियाँ सम चाहिए; आयलर पथ हेतु ठीक दो विषम। आयलर कोरों की बात है, हैमिल्टन शीर्षों की, और सम-विषमता कसौटी केवल आयलर के पास है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. ऐसे कितने सरल ग्राफ हैं जिनमें 5 शीर्षों में प्रत्येक की कोटि ठीक 3 हो?

    1. ठीक एक
    2. ठीक दो
    3. कोई नहीं — ऐसा ग्राफ विद्यमान नहीं
    4. अनंत
    उत्तर देखें

    उत्तर: C — कोई नहीं — ऐसा ग्राफ विद्यमान नहीं

    हस्तमिलन प्रमेयिका से कोटि-योग कोर-संख्या का दुगुना है, अतः उसे सम होना ही चाहिए। यहाँ योग 5 × 3 = 15 है, जो विषम है — अतः ऐसा ग्राफ विद्यमान नहीं, और उत्तर हेतु रचना का प्रयास आवश्यक नहीं। साथ रखने योग्य सामान्य रूप: n शीर्षों पर k-नियमित ग्राफ केवल तब विद्यमान है जब nk सम हो, इसीलिए 3-नियमित ग्राफ 4, 6, 8 … शीर्षों पर होते हैं और विषम संख्या पर कभी नहीं। विकल्प D सैद्धांतिक रूप से भी हटाया जा सकता है — नियत शीर्ष-समुच्चय पर परिमित ही ग्राफ होते हैं, क्योंकि ग्राफ अधिकतम n(n − 1)/2 संभव कोरों का उपसमुच्चय है।

  2. 5 शीर्षों पर चक्र की रंगन-संख्या है:

    1. 2
    2. 3
    3. 4
    4. 5
    उत्तर देखें

    उत्तर: B — 3

    चक्र में दो रंग एकांतर करते हुए घूमें: पाँच चरणों के बाद आप आरंभ पर लौटते हैं और किसी कोर के दोनों सिरों पर वही रंग लगा होता है, अतः दो रंग असंभव हैं — विषम चक्र द्विभाजित नहीं होता। तीन पर्याप्त हैं: चार शीर्ष एकांतर रंगें और पाँचवें को तीसरा रंग दें। अतः χ(C₅) = 3। विकल्प A सम चक्र हेतु उत्तर है, और 6 के बजाय 5 चुनने का पूरा मुद्दा उसे देना ही है। विकल्प D, χ(K₅) है, जो उसी शीर्ष-संख्या पर भिन्न ग्राफ है — C₅ के 5 कोर हैं और K₅ के 10, और जब प्रश्न केवल शीर्ष-संख्या नामित करे तब दोनों को भ्रमित न करना सावधानी योग्य है।

  3. किसी संबद्ध सरल ग्राफ के 6 शीर्ष व 6 कोर हैं। निम्नलिखित में कौन अवश्य सत्य है?

    1. वह वृक्ष है
    2. उसमें कम-से-कम एक चक्र है
    3. वह द्विभाजित है
    4. उसका कोई शीर्ष कोटि 5 का है
    उत्तर देखें

    उत्तर: B — उसमें कम-से-कम एक चक्र है

    6 शीर्षों पर वृक्ष के ठीक 5 कोर होते हैं, और उससे अधिक कोरों वाले संबद्ध ग्राफ में चक्र होना ही चाहिए — 6 > 5, अतः उसमें कम-से-कम एक चक्र है। यह विकल्प A को भी सीधे हटा देता है। विकल्प C विवश नहीं: वृक्ष में एक कोर जोड़ने से विषम चक्र बन सकता है, और विषम चक्र वाला ग्राफ द्विभाजित नहीं, अतः द्विभाजनीयता संभव है पर आवश्यक नहीं। विकल्प D भी विवश नहीं — कोटि-योग 12 है, जो 6-चक्र में 2, 2, 2, 2, 2, 2 के रूप में फैल सकता है, जहाँ कोई शीर्ष कोटि 2 से ऊपर नहीं। उपयोगी आदत यह है कि पहले कोर-संख्या की n − 1 से तुलना करें: उससे कम पर ग्राफ संबद्ध नहीं हो सकता, उस पर वह वृक्ष है, उससे अधिक पर चक्र है।

  4. किसी संबद्ध ग्राफ के ठीक दो शीर्षों की कोटि विषम है। अतः उसमें है:

    1. आयलर परिपथ पर आयलर पथ नहीं
    2. आयलर पथ पर आयलर परिपथ नहीं
    3. आयलर परिपथ व हैमिल्टन चक्र दोनों
    4. न आयलर पथ न आयलर परिपथ
    उत्तर देखें

    उत्तर: B — आयलर पथ पर आयलर परिपथ नहीं

    ठीक दो विषम-कोटि शीर्ष ठीक वही शर्त है जो खुले आयलर पथ हेतु है, और वे दो शीर्ष अनिवार्यतः उसके सिरे होते हैं। बंद आयलर परिपथ हेतु प्रत्येक कोटि सम चाहिए, अतः वह हट जाता है। विकल्प C ऐसा हैमिल्टन-दावा जोड़ता है जिसका यहाँ कोई आधार नहीं: आयलर की शर्तें हैमिल्टनीयता के विषय में कुछ नहीं कहतीं, जिसकी कोई ज्ञात कोटि-कसौटी नहीं और जिसका निर्णय NP-पूर्ण है — दोनों को साथ देना इस प्रकरण का मानक भ्रामक विकल्प है। यह भी ध्यान दें कि "ठीक एक विषम शीर्ष" कभी विचारणीय स्थिति नहीं, क्योंकि विषम-कोटि शीर्षों की संख्या सदा सम होती है।

  5. द्विभाजित ग्राफ में अधिकतम मेल का आकार न्यूनतम शीर्ष-आवरण के आकार के बराबर होता है। यह है:

    1. आयलर प्रमेय
    2. कोनिग प्रमेय
    3. केली सूत्र
    4. प्रत्येक ग्राफ हेतु सत्य, केवल द्विभाजित हेतु नहीं
    उत्तर देखें

    उत्तर: B — कोनिग प्रमेय

    यह कोनिग प्रमेय है, और उसमें "द्विभाजित" शब्द भार वहन करता है। किसी भी ग्राफ में अधिकतम मेल न्यूनतम शीर्ष-आवरण से अधिक नहीं, क्योंकि प्रत्येक मेलित कोर को पृथक आवरण-शीर्ष चाहिए; कोनिग कहता है कि द्विभाजित ग्राफ में दोनों बराबर हैं। विकल्प D जाल है और असत्य: त्रिभुज लें, जिसका अधिकतम मेल 1 है जबकि न्यूनतम शीर्ष-आवरण 2। वह एक प्रत्युदाहरण याद रखने योग्य है क्योंकि वह सबसे छोटा विषम चक्र भी है, और द्विभाजनीयता ठीक विषम चक्रों को ही वर्जित करती है। व्यावहारिक उपयोग प्रमाण का लघु-मार्ग है — समान आकार का मेल व आवरण दिखा दें और दोनों इष्टतम हैं, आगे कोई खोज नहीं।

  6. n ≥ 2 शीर्षों पर प्रत्येक वृक्ष T हेतु निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. T के ठीक n − 1 कोर हैं
    2. T द्विभाजित है
    3. T के कम-से-कम दो शीर्ष कोटि 1 के हैं
    4. T में हैमिल्टन चक्र है
    उत्तर देखें

    उत्तर: A — T के ठीक n − 1 कोर हैं; B — T द्विभाजित है; C — T के कम-से-कम दो शीर्ष कोटि 1 के हैं

    तीन सत्य हैं। A परिभाषा-गणना है। B सत्य है क्योंकि वृक्ष में चक्र ही नहीं होते, अतः विषम चक्र निश्चित ही नहीं — प्रत्येक वृक्ष 2-रंगनीय है। C पर्ण-प्रमेयिका है: कोटि-योग 2(n − 1) है, अतः औसत कोटि 2 से कम है, और ऐसा संबद्ध ग्राफ जिसमें दो से कम शीर्ष कोटि 1 के हों उससे अधिक हो जाता। केवल D विफल है, और वह उपलब्ध सर्वाधिक सीधे कारण से विफल होता है: हैमिल्टन चक्र चक्र है, और वृक्ष में कोई नहीं। ध्यान दें D वही एक विकल्प है जो परिभाषा से आगे जाने के बजाय उसका विरोध करता है — ऐसे MSQ से गुजरने का सबसे तेज़ मार्ग पहले प्रत्येक विकल्प को परिभाषा से जाँचना और उसके बाद ही प्रत्युदाहरण खोजना है।

  7. 5 शीर्षों पर भिन्न लेबल-युक्त वृक्षों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 125

    केली सूत्र n शीर्षों पर n(n−2) लेबल-युक्त वृक्ष देता है, अतः 5³ = 125। घातांक पर भरोसा करने के बजाय सबसे छोटी स्थिति पर जाँचें: n = 3 पर सूत्र 3¹ = 3 देता है, और तीन शीर्षों पर वास्तव में तीन लेबल-युक्त वृक्ष हैं, मध्य शीर्ष के प्रत्येक चुनाव हेतु एक — जो n − 1 के बजाय n − 2 की पुष्टि करता है। चार शीर्ष 4² = 16 देते हैं। ध्यान दें क्या गिना जा रहा है: लेबल-युक्त शीर्षों पर वृक्ष, जहाँ पुनः लेबल करने पर भिन्न वृक्ष बनता है। पाँच शीर्षों पर लेबल-रहित वृक्ष-आकारों की संख्या 3 है, बहुत छोटी व असंबद्ध गिनती, और प्रश्न सदा स्पष्ट करता है कि उसे कौन चाहिए।

  8. किसी 3-नियमित सरल ग्राफ के 6 शीर्ष हैं। उसके कोरों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 9

    कोटि-योग 6 × 3 = 18 है, और हस्तमिलन प्रमेयिका कहती है कि वह 2|E| के बराबर है, अतः |E| = 9। साथ रखने योग्य सामान्य रूप nk/2 है, और वह दो काम करता है: nk सम होने पर कोर गिनता है और nk विषम होने पर अनस्तित्व सिद्ध करता है। 5 शीर्षों पर 3-नियमित ग्राफ को 15/2 कोर चाहिए होते, इसीलिए इस अध्याय के पूर्व प्रश्न में ऐसा ग्राफ नहीं था। K₃,₃ तथा प्रिज़्म ग्राफ दोनों छह शीर्षों पर नौ कोरों सहित 3-नियमित हैं, अतः गिनती ग्राफ को निर्धारित नहीं करती — ऐसे कितने ग्राफ पूछने वाला प्रश्न इससे कठिन व भिन्न प्रश्न है।