ग्राफ भ्रमण, न्यूनतम विस्तारक वृक्ष व लघुतम पथ

तीन कलनविधि-कुल, और प्रश्न अधिकांशतः इस विषय में हैं कि आपके सामने के ग्राफ पर कौन-सी अनुमत है। भ्रमण सबसे सरल हैं: सन्निकटता सूची पर BFS व DFS दोनों की लागत O(V + E) है, और महत्वपूर्ण अंतर यह है कि वे क्या निकालते हैं। BFS दूरी से खोजता है, अतः अभारित ग्राफ पर वह लघुतम पथ निःशुल्क देता है; DFS गहराई से खोजता है, और वही उसे चक्र-संसूचन, सांस्थितिक वर्गीकरण व प्रबल संबद्ध घटकों का आधार बनाता है। भारित ग्राफ पर कोई भी लघुतम पथ नहीं देता, और वहाँ BFS की ओर बढ़ना मानक त्रुटि है। तत्पश्चात् न्यूनतम विस्तारक वृक्ष आते हैं, दो लोभी कलनविधियों सहित जो दोनों सही हैं — क्रुस्कल वर्गीकृत कोर-भार से, प्रिम एक वृक्ष बढ़ाकर — तथा एक तथ्य यथार्थ रूप से कहने योग्य है: MST का भार सदा अद्वितीय होता है, MST स्वयं आवश्यक रूप से नहीं। जिस ग्राफ के सभी कोरों के भार भिन्न हों उसका ठीक एक MST होता है; बराबरी वाले के कई हो सकते हैं, सब समान कुल के। लघुतम पथ वहाँ हैं जहाँ अनुमति का प्रश्न सर्वाधिक काटता है। डिजस्ट्रा O(E log V) है और ऋण कोरों पर गलत — धीमा नहीं, गलत — क्योंकि वह किसी शीर्ष को पॉप होते ही अंतिम कर देता है और बाद का ऋण कोर उस निर्णय को काट सकता है। बेलमैन–फोर्ड O(VE) है और ऋण कोर सँभालता है, तथा अनंत चक्र के बजाय ऋण चक्र का पता लगाता है। फ़्लॉयड–वॉरशॉल O(V³) है और तीन नेस्टेड चक्रों में सभी युग्म देता है। उनमें चुनाव इस खंड का प्रिय प्रश्न है, और उत्तर ग्राफ के दो गुणों से तय होता है — कोई भार ऋण है या नहीं, तथा आपको एक स्रोत चाहिए या सभी।

BFS व DFS: समान लागत, भिन्न उपयोग

प्रत्येक भ्रमण वस्तुतः किस हेतु है
पक्षBFSDFS
लागत (सन्निकटता सूची)O(V + E)O(V + E)
आँकड़ा संरचनाकतारस्टैक या पुनरावर्तन
लघुतम पथ देता हैहाँ, यदि अभारितनहीं
उसके अभिलाक्षणिक उपयोगस्तर क्रम, द्विभाजित परीक्षणचक्र, सांस्थितिक वर्गीकरण, SCC
⚠️ BFS लघुतम पथ केवल तब देता है जब प्रत्येक कोर की लागत समान हो
BFS शीर्षों को छलाँग-गणना के क्रम में देखता है, जो लघुतम पथ ठीक तब है जब प्रत्येक छलाँग की लागत एक हो। कोरों पर भार रखें और वह तुरंत टूट जाता है: भार 1 + 1 का दो-छलाँग पथ भार 5 के एक-छलाँग पथ को हरा देता है, और BFS एक-छलाँग मार्ग पहले अंतिम कर चुका होगा। उपचार BFS की मरम्मत नहीं अपितु उसी हेतु बनी कलनविधि का प्रयोग है — डिजस्ट्रा मूलतः साधारण कतार के बजाय प्राथमिकता-कतार सहित BFS है, और यह याद रखने का उपयोगी तरीका है कि उसकी लागत O(V + E) के बजाय O(E log V) क्यों है। भारों का उल्लेख करके BFS को विकल्प के रूप में देता प्रश्न यही जाँच रहा है और कुछ नहीं।

न्यूनतम विस्तारक वृक्ष: अद्वितीय भार, बहुवचन वृक्ष

A, B, C, D पर वह ग्राफ लें जिसमें A–B, B–C व A–C सभी भार 1 के हों, तथा C–D भार 2 का। क्रुस्कल तीन इकाई-कोरों में दो लेता है — कोई भी दो A, B, C सबको जोड़ देते हैं — और तत्पश्चात् C–D, कुल भार 4। परंतु कौन-से दो यह स्वतंत्र चुनाव है, अतः तीन भिन्न न्यूनतम विस्तारक वृक्ष हैं, सब भार 4 के।

🎯 वृक्ष अद्वितीय न होने पर भी भार अद्वितीय क्यों
"न्यूनतम" संख्या का गुण है, अतः प्रत्येक न्यूनतम विस्तारक वृक्ष का कुल परिभाषा से समान है — यदि दो विस्तारक वृक्षों के भार भिन्न होते, तो भारी वाला न्यूनतम नहीं था। जो बाध्य नहीं है वह समान-भार कोरों में चुनाव है, और अ-अद्वितीयता का सम्पूर्ण कारण वही है। दो परिणाम परीक्षणीय हैं। यदि सभी कोर-भार भिन्न हों तो MST अद्वितीय है — तोड़ने योग्य बराबरी कभी नहीं होती। और दोहराए भारों वाले ग्राफ का "वह न्यूनतम विस्तारक वृक्ष" पूछता प्रश्न कुगठित है, जबकि उसका भार पूछता प्रश्न ठीक है, अतः बराबरी देखना बताता है कि किस प्रकार का उत्तर चाहा जा रहा है। वही तर्क लघुतम पथों पर लागू है: दूरी अद्वितीय है, पथ आवश्यक रूप से नहीं।
क्रुस्कल बनाम प्रिम
पक्षक्रुस्कलप्रिम
बढ़ाता हैवह वन जो विलीन होता हैआरंभ शीर्ष से एक वृक्ष
आवश्यकतावर्गीकृत कोर + यूनियन–फ़ाइंडशीर्षों की प्राथमिकता-कतार
लागतO(E log E)द्विआधारी ढेर से O(E log V)
अधिक उपयुक्तविरल ग्राफघने ग्राफ

लघुतम पथ, तथा प्रत्येक कलनविधि क्या मान सकती है

लघुतम-पथ कलनविधि चुनना
कलनविधिलागतऋण कोर सँभालती है?स्रोत
BFSO(V + E)केवल अभारितएक
डिजस्ट्राO(E log V)नहीं — गलत उत्तर देती हैएक
बेलमैन–फोर्डO(VE)हाँ, तथा ऋण चक्रों का पता लगाती हैएक
फ़्लॉयड–वॉरशॉलO(V³)हाँ (ऋण चक्र न हों)सभी युग्म
⚠️ ऋण कोर पर डिजस्ट्रा गलत है, धीमी नहीं — ग्राफ यह है
तीन शीर्ष। A→B की लागत 1, A→C की 2, C→B की −2। A से डिजस्ट्रा पहले B को पॉप करता है, दूरी 1 पर, और उसे अंतिम कर देता है — कलनविधि की केंद्रीय मान्यता वही है, कि सबसे छोटी अस्थायी दूरी बाद में कभी सुधारी नहीं जा सकती। परंतु B तक वास्तविक लघुतम पथ A→C→B है, 2 + (−2) = 0 पर। डिजस्ट्रा 1 बताता है। विफलता धीमा उत्तर या अनंत चक्र नहीं; वह आत्मविश्वास से गलत संख्या है, और इसीलिए "डिजस्ट्रा प्रयोग करें व प्रत्येक भार में बड़ा अचर जोड़ें" भी उसे ठीक नहीं करता — प्रति कोर अचर जोड़ना अधिक कोरों वाले पथों को दंडित करता है और बदल देता है कि कौन-सा पथ लघुतम है। ऋण कोरों हेतु बेलमैन–फोर्ड चाहिए, और अनुमति का सम्पूर्ण प्रश्न वही है।

शेष चुनाव एक स्रोत व सभी के बीच है। प्रत्येक शीर्ष से चलाया बेलमैन–फोर्ड O(V²E) लेता है, जो घने ग्राफ पर जहाँ E ≈ V² है O(V⁴) है — फ़्लॉयड–वॉरशॉल के O(V³) से बुरा, जो सन्निकटता आव्यूह पर तीन नेस्टेड चक्र हैं। विरल ग्राफ पर तुलना उलट जाती है। अतः सभी-युग्म प्रश्न भी घनत्व पर लौट आता है, ठीक जैसे निरूपण का चुनाव लौटा था।

मुख्य बिंदु

  • BFS व DFS दोनों O(V + E) लेते हैं; BFS लघुतम पथ केवल अभारित ग्राफ पर देता है।
  • DFS चक्र-संसूचन, सांस्थितिक वर्गीकरण व प्रबल संबद्ध घटकों का आधार है।
  • MST का भार सदा अद्वितीय है; MST ठीक तब अद्वितीय है जब सभी कोर-भार भिन्न हों।
  • क्रुस्कल यूनियन–फ़ाइंड से O(E log E) है; प्रिम द्विआधारी ढेर से O(E log V)।
  • डिजस्ट्रा ऋण कोरों पर गलत है, धीमी नहीं — वह शीर्ष को पॉप होते ही अंतिम कर देती है।
  • प्रत्येक भार में अचर जोड़ना उसे ठीक नहीं करता: वह अधिक कोरों वाले पथों को दंडित करता है।
  • बेलमैन–फोर्ड O(VE) है, ऋण कोर सँभालती है, तथा ऋण चक्रों का पता लगाती है।
  • फ़्लॉयड–वॉरशॉल सभी युग्म O(V³) में देती है — घने ग्राफ पर बेलमैन–फोर्ड की V बार से अच्छा।

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

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

  1. एक दिष्ट ग्राफ में कोर A→B भार 1, A→C भार 2 तथा C→B भार −2 के हैं। A से डिजस्ट्रा, B तक दूरी बताता है:

    1. 0, सही उत्तर
    2. 1, जो गलत है — वास्तविक दूरी 0 है
    3. वह अनंत काल चलता है
    4. −2
    उत्तर देखें

    उत्तर: B — 1, जो गलत है — वास्तविक दूरी 0 है

    डिजस्ट्रा निकटतम अस्थायी शीर्ष पॉप करके उसे अंतिम कर देता है। A से B अस्थायी रूप से 1 है और C, 2, अतः B पहले पॉप होकर 1 पर नियत हो जाता है — कोर C→B देखे जाने से पूर्व ही। वास्तविक लघुतम पथ A→C→B है 2 + (−2) = 0 पर। अतः डिजस्ट्रा आत्मविश्वास से गलत संख्या लौटाता है, और महत्वपूर्ण अंश वही है: वह अटकता नहीं (विकल्प C) और समस्या का पता नहीं लगाता। इसीलिए ऋण कोरों हेतु बेलमैन–फोर्ड चाहिए, और इसीलिए प्रत्येक भार में अचर जोड़ने का मानक "उपचार" भी विफल है — प्रति कोर अचर लंबे पथों को दंडित करता है और बदल सकता है कि कौन-सा पथ लघुतम है।

  2. किसी भारित ग्राफ के कुछ कोरों का भार समान है। कौन-सा कथन सही है?

    1. MST तथा उसका भार दोनों अ-अद्वितीय हो सकते हैं
    2. MST अ-अद्वितीय हो सकता है परंतु उसका भार अद्वितीय है
    3. दोनों सदा अद्वितीय हैं
    4. भार अ-अद्वितीय हो सकता है परंतु वृक्ष अद्वितीय है
    उत्तर देखें

    उत्तर: B — MST अ-अद्वितीय हो सकता है परंतु उसका भार अद्वितीय है

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

  3. ऋण कोरों से रहित भारित ग्राफ में एक स्रोत से लघुतम पथ ढूँढ़ने हेतु सर्वोत्तम चुनाव है:

    1. BFS, O(V + E) पर
    2. डिजस्ट्रा, O(E log V) पर
    3. फ़्लॉयड–वॉरशॉल, O(V³) पर
    4. बेलमैन–फोर्ड, O(VE) पर
    उत्तर देखें

    उत्तर: B — डिजस्ट्रा, O(E log V) पर

    डिजस्ट्रा। BFS सस्ता है पर सही केवल तब जब प्रत्येक कोर की लागत समान हो, अतः वह भारित ग्राफ पर लागू नहीं। बेलमैन–फोर्ड यहाँ सही है पर उस व्यापकता — ऋण कोर — हेतु O(VE) चुकाता है जो इस ग्राफ को चाहिए नहीं। फ़्लॉयड–वॉरशॉल पूछी गई से बड़ी समस्या हल करता है, एक स्रोत के बजाय सभी युग्म, और उसके लिए O(V³) लेता है। बनाने योग्य आदत यह है कि प्रश्न से दो गुण पहले पढ़ें: कोई भार ऋण है क्या, और मुझे एक स्रोत चाहिए या सभी? वे दो उत्तर किसी जटिलता की तुलना से पूर्व ही कलनविधि चुन देते हैं।

  4. BFS व DFS के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

    1. दोनों सन्निकटता सूची पर O(V + E) में चलते हैं
    2. BFS अभारित ग्राफ में लघुतम पथ ढूँढ़ता है
    3. DFS सांस्थितिक वर्गीकरण का आधार है
    4. BFS किसी भी भारित ग्राफ में लघुतम पथ ढूँढ़ता है
    उत्तर देखें

    उत्तर: A — दोनों सन्निकटता सूची पर O(V + E) में चलते हैं; B — BFS अभारित ग्राफ में लघुतम पथ ढूँढ़ता है; C — DFS सांस्थितिक वर्गीकरण का आधार है

    A, B व C। दोनों भ्रमण प्रत्येक शीर्ष व प्रत्येक कोर को एक बार स्पर्श करते हैं, अतः O(V + E) (A)। BFS छलाँग-गणना के क्रम में खोजता है, जो लघुतम पथ ठीक तब है जब सभी कोरों की लागत समान हो (B)। DFS का समापन-क्रम उलटा एक सांस्थितिक क्रम है, इसीलिए वह उस कलनविधि तथा चक्र-संसूचन व प्रबल संबद्ध घटकों के नीचे है (C)। D असत्य है और प्रश्न का अभिप्राय वही है — कोरों पर असमान भार रखें और दो-छलाँग सस्ता पथ एक-छलाँग महँगे को हरा देता है, जिसे BFS पहले ही अंतिम कर चुका होगा। डिजस्ट्रा उपचार है, और वह मूलतः प्राथमिकता-कतार सहित BFS है।

  5. चार शीर्षों के ग्राफ में कोर A–B, B–C व A–C प्रत्येक भार 1 का, तथा C–D भार 2 का है। उसके न्यूनतम विस्तारक वृक्ष का भार क्या है?

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

    उत्तर देखें

    उत्तर: 4

    चार शीर्षों के विस्तारक वृक्ष में ठीक तीन कोर होते हैं। तीन इकाई-कोरों में दो A, B व C को जोड़ते हैं — कोई भी दो चलेंगे — और D तक पहुँचने का एकमात्र मार्ग C–D है, अतः कुल 1 + 1 + 2 = 4। ध्यान दें प्रश्न सावधानी से क्या पूछता है: भार, जो अद्वितीय है। "वह" वृक्ष पूछना कुगठित होता, क्योंकि तीन समान कोरों में स्वतंत्र चुनाव तीन भिन्न न्यूनतम विस्तारक वृक्ष देता है, सब भार 4 के। 5 उत्तर देने का अर्थ प्रायः तीनों इकाई-कोर लेना है, जो एक चक्र होगा और अतः वृक्ष नहीं।

  6. E ≈ V² वाले घने ग्राफ पर सभी-युग्म लघुतम पथ निकालना सर्वाधिक सस्ता है:

    1. प्रत्येक शीर्ष से बेलमैन–फोर्ड
    2. फ़्लॉयड–वॉरशॉल
    3. प्रत्येक शीर्ष से BFS
    4. क्रुस्कल
    उत्तर देखें

    उत्तर: B — फ़्लॉयड–वॉरशॉल

    फ़्लॉयड–वॉरशॉल O(V³) है — आव्यूह पर तीन नेस्टेड चक्र। प्रत्येक शीर्ष से बेलमैन–फोर्ड O(V·VE) = O(V²E) है, और E ≈ V² के साथ वह O(V⁴) है, पूरे V गुणक से बुरा। विकल्प C केवल अभारित ग्राफों हेतु वैध है। विकल्प D पूर्णतः भिन्न समस्या हल करता है — न्यूनतम विस्तारक वृक्ष लघुतम-पथ संरचना नहीं है, और MST में दो शीर्षों के बीच का पथ लघुतम पथ होना आवश्यक नहीं, जो स्वयं में जानने योग्य तथ्य है। ध्यान दें कि विरल ग्राफ पर तुलना उलट जाती है, अतः यहाँ घनत्व तय करता है ठीक जैसे उसने निरूपण का चुनाव तय किया था।

  7. बेलमैन–फोर्ड, डिजस्ट्रा से वरीय है जब:

    1. ग्राफ अत्यंत बड़ा हो
    2. कुछ कोर-भार ऋण हों
    3. सभी-युग्म दूरियाँ चाहिए हों
    4. ग्राफ अदिष्ट हो
    उत्तर देखें

    उत्तर: B — कुछ कोर-भार ऋण हों

    ऋण कोर-भार, और O(VE) चुकाने योग्य एकमात्र कारण वही है — डिजस्ट्रा अनंतस्पर्शी रूप से तेज़ है और अन्यथा वही चुनाव होता। बेलमैन–फोर्ड किसी शीर्ष को पॉप होने पर प्रतिबद्ध करने के बजाय प्रत्येक कोर को V − 1 बार शिथिल करता है, अतः बाद का ऋण कोर तब भी दूरी सुधार सकता है; और एक और शिथिलन जो तब भी कुछ सुधारे वह ऋण चक्र सिद्ध करता है, जिसे वह चक्र में घूमने के बजाय बताता है। विकल्प A उलटी दिशा दिखाता है, क्योंकि बड़ा ग्राफ तेज़ कलनविधि का पक्ष लेता है। विकल्प C, फ़्लॉयड–वॉरशॉल का काम है।

  8. यदि किसी संबद्ध ग्राफ में प्रत्येक कोर-भार भिन्न हो, तो:

    1. न्यूनतम विस्तारक वृक्ष अद्वितीय है
    2. तब भी कई न्यूनतम विस्तारक वृक्ष हो सकते हैं
    3. क्रुस्कल व प्रिम भिन्न भार के वृक्ष लौटा सकते हैं
    4. ग्राफ में कोई चक्र नहीं है
    उत्तर देखें

    उत्तर: A — न्यूनतम विस्तारक वृक्ष अद्वितीय है

    अद्वितीय। अ-अद्वितीयता पूर्णतः बराबरी से आती है: जब दो कोरों का भार समान हो, कोई भी लिया जा सकता है और दो भिन्न वृक्ष निकलते हैं। प्रत्येक बराबरी हटाएँ और प्रत्येक लोभी चरण के पास ठीक एक सर्वोत्तम चाल होती है, अतः क्रुस्कल व प्रिम न केवल भार पर सहमत होते हैं — जो वे सदा होते हैं — अपितु वही वृक्ष लौटाते हैं। विकल्प C किसी भी परिस्थिति में असंभव है, क्योंकि दोनों कलनविधियाँ सही हैं और प्रत्येक MST का कुल परिभाषा से समान है। विकल्प D भारों के गुण को संरचना के गुण से भ्रमित करता है: भिन्न भारों वाले ग्राफ में जितने चाहे चक्र हो सकते हैं।