ग्राफ़ और कंप्यूटर उन्हें कैसे रखता है
ग्राफ़ में शीर्ष (नोड) और किनारे (कड़ियाँ) होते हैं। किनारे दिष्ट (एकतरफ़ा तीर) हो सकते हैं और उन पर भार (दूरी, लागत, समय या क्षमता) हो सकता है।
- आसन्नता आव्यूह (adjacency matrix): तालिका जिसमें पंक्ति i, स्तंभ j पर किनारे i→j का भार (या 0) होता है। एक किनारा जाँचना तेज़; n² जगह लेता है।
- आसन्नता सूची (adjacency list): हर शीर्ष अपने पड़ोसियों की सूची रखता है। कम किनारों वाले ग्राफ़ में जगह बचती है।
किसी शीर्ष की घात उस पर मिलने वाले किनारों की संख्या है। 3D ग्राफ़ में C की घात 4 है।
ट्रैवर्सल: चौड़ाई-प्रथम और गहराई-प्रथम
चौड़ाई-प्रथम खोज (BFS)
- शुरुआती शीर्ष को कतार में डालिए और देखा हुआ चिह्नित कीजिए।
- कतार के आगे वाला शीर्ष निकालिए।
- उसके हर अनदेखे पड़ोसी को कतार के पीछे जोड़िए और चिह्नित कीजिए।
- कतार ख़ाली होने तक दोहराइए।
बिना भार वाले ग्राफ़ में BFS सबसे कम किनारों वाला रास्ता देती है। उपयोग: भूलभुलैया का छोटा रास्ता, दोस्तों के दोस्त, वेब क्रॉलर।
गहराई-प्रथम खोज (DFS)
- शुरुआती शीर्ष पर जाइए और चिह्नित कीजिए।
- किसी अनदेखे पड़ोसी पर जाकर वहीं से दोहराइए (ढेर में डालिए, या रिकर्शन)।
- बंद सिरे पर उस आख़िरी शीर्ष तक लौटिए (pop) जिसका कोई पड़ोसी अनदेखा है।
उपयोग: भूलभुलैया और पहेलियाँ, चक्र ढूँढ़ना, ग्राफ़ जुड़ा है या नहीं, कामों का टोपोलॉजिकल क्रम।
आसन्नता सूची के साथ दोनों का समय V + E (शीर्ष + किनारे) के अनुपात में होता है।
ट्री ट्रैवर्सल: प्री-ऑर्डर, इन-ऑर्डर, पोस्ट-ऑर्डर
ट्री बिना चक्र वाला जुड़ा ग्राफ़ है। बाइनरी ट्री में DFS जड़ (root) पर तीन अलग समय पर जा सकती है:
- प्री-ऑर्डर: जड़, बायाँ, दायाँ – ट्री की नकल बनाने या प्रीफ़िक्स संकेतन लिखने में।
- इन-ऑर्डर: बायाँ, जड़, दायाँ – बाइनरी सर्च ट्री के मान बढ़ते क्रम में देता है।
- पोस्ट-ऑर्डर: बायाँ, दायाँ, जड़ – ट्री मिटाने या पोस्टफ़िक्स (रिवर्स पोलिश) व्यंजक हल करने में।
उदाहरण: जड़ 8, बायाँ बच्चा 3 (उसके बच्चे 1 और 6), दायाँ बच्चा 10। प्री-ऑर्डर: 8, 3, 1, 6, 10। इन-ऑर्डर: 1, 3, 6, 8, 10। पोस्ट-ऑर्डर: 1, 6, 3, 10, 8।
डाइक्स्ट्रा का सबसे छोटा रास्ता एल्गोरिद्म
- शुरुआती शीर्ष को दूरी 0 और बाक़ी सबको ∞ दीजिए।
- सबसे छोटी दूरी वाले अपक्के शीर्ष को पक्का कीजिए (अब उसकी दूरी अंतिम है)।
- हर पड़ोसी के लिए, अगर (पक्की दूरी + किनारे का भार) उसकी मौजूदा दूरी से कम है, तो उसे बदलिए और लिखिए कि कहाँ से आया।
- सब पक्के होने तक दोहराइए। "कहाँ से आया" पीछे पढ़कर रास्ता निकालिए।
3D ग्राफ़ में A से: A = 0, C = 2, B = 3 (C से होकर, सीधी सड़क 4 की नहीं), D = 8, E = 10, F = 13। डाइक्स्ट्रा तभी चलता है जब कोई भार ऋणात्मक न हो। प्राथमिकता कतार के साथ इसका समय लगभग (V + E) log V है।
न्यूनतम स्पैनिंग ट्री, रूट इंस्पेक्शन और ट्रैवलिंग सेल्सपर्सन
न्यूनतम स्पैनिंग ट्री (MST)
स्पैनिंग ट्री सब V शीर्षों को V − 1 किनारों से, बिना चक्र के जोड़ता है। MST का कुल भार सबसे कम होता है।
- क्रुस्कल: किनारों को भार से क्रम में लगाइए; हर किनारा जोड़िए, जब तक वह चक्र न बनाए।
- प्रिम: कहीं से शुरू कीजिए; बार-बार वह सबसे सस्ता किनारा जोड़िए जो ट्री को नए शीर्ष से जोड़े (दूरी तालिका पर आसान)।
3D ग्राफ़ में: BC 1, AC 2, DE 2, EF 3, BD 5 → कुल 13 km (AB 4 छोड़ा गया: चक्र बनता)।
रूट इंस्पेक्शन (चाइनीज़ पोस्टमैन)
हर किनारे पर कम से कम एक बार चलने वाला सबसे छोटा बंद रास्ता। अगर सब घातें सम हैं, उत्तर = कुल भार। वरना विषम घात वाले शीर्षों को जोड़ों में बाँटकर उनके बीच के सबसे छोटे रास्ते जोड़िए। 3D ग्राफ़ में B और E विषम हैं; कुल भार 41 + सबसे छोटा B–E रास्ता 7 = 48 km।
ट्रैवलिंग सेल्सपर्सन (TSP)
हर शीर्ष पर एक बार जाकर लौटने वाला सबसे छोटा चक्कर। इसका कोई तेज़ सटीक तरीका ज्ञात नहीं, इसलिए सीमाएँ निकालते हैं:
- ऊपरी सीमा: निकटतम-पड़ोसी चक्कर (हमेशा सबसे पास के अनदेखे शीर्ष पर जाइए)।
- निचली सीमा: एक शीर्ष हटाइए, बाक़ी का MST निकालिए, फिर हटाए शीर्ष के दो सबसे छोटे किनारे जोड़िए।
सबसे अच्छा चक्कर दोनों सीमाओं के बीच होता है।
नेटवर्क प्रवाह: अधिकतम प्रवाह और न्यूनतम कट
प्रवाह नेटवर्क एक दिष्ट ग्राफ़ है जिसमें हर चाप की क्षमता (अधिकतम कितना ले जा सकता है) होती है, जैसे पाइप या सड़कें। प्रवाह स्रोत S से निकलकर सिंक T तक पहुँचता है। बीच के हर शीर्ष पर अंदर आया प्रवाह = बाहर गया प्रवाह।
- कट शीर्षों को दो भागों में बाँटता है, एक में S और दूसरे में T। इसकी क्षमता = S वाले भाग से T वाले भाग की ओर जाने वाले चापों की क्षमताओं का योग।
- अधिकतम-प्रवाह न्यूनतम-कट प्रमेय: सबसे बड़ा संभव प्रवाह = सबसे छोटे कट की क्षमता।
- प्रवाह वृद्धि: किसी वैध प्रवाह से शुरू कीजिए, S से T तक ख़ाली क्षमता वाला रास्ता ढूँढ़िए (वह पहले से भरे चाप पर उल्टा भी धकेल सकता है), उस पर प्रवाह जोड़िए, तब तक दोहराइए जब तक ऐसा रास्ता न बचे।
- कई स्रोत या सिंक? हर स्रोत से जुड़ा एक सुपर-स्रोत और एक सुपर-सिंक जोड़िए, असीमित क्षमता के साथ।
- किसी चाप की निचली क्षमता भी हो सकती है (उसे कम से कम उतना ले जाना ही है)। प्रवाह तभी संभव है जब हर चाप निचली और ऊपरी क्षमता के बीच रहे।
उदाहरण: S→A 4, S→B 3, A→B 2, A→T 3, B→T 4। S-A-T पर 3, S-B-T पर 3, S-A-B-T पर 1 भेजिए: प्रवाह 7। कट {S} | {A, B, T} की क्षमता 4 + 3 = 7, इसलिए 7 ही अधिकतम है।
खुद करके देखिए: खुद एल्गोरिद्म बनिए
अपनी गली के 6 घरों के लिए 6 बिंदु बनाइए और उन्हें रेखाओं से जोड़िए; कदमों में दूरी लिखिए। अपने घर से तालिका बनाकर हाथ से डाइक्स्ट्रा चलाइए, फिर 'खुद करके देखिए' वाले चरण में (शुरुआत A) जाँचिए। फिर हर घर को केबल से जोड़ने का सबसे सस्ता तरीका (MST) निकालिए।
मुख्य सूत्र और परिभाषाएँ
- BFS कतार (पहले आओ, पहले जाओ) इस्तेमाल करती है; DFS ढेर (आख़िर में आया, पहले गया) या रिकर्शन
- डाइक्स्ट्रा अपडेट: अगर d(v) + w(v,u) < d(u) तो d(u) = d(v) + w(v,u)
- V शीर्षों के स्पैनिंग ट्री में V − 1 किनारे होते हैं
- रूट इंस्पेक्शन = कुल भार + विषम शीर्षों को जोड़ने वाले सबसे छोटे रास्ते
- अधिकतम प्रवाह = न्यूनतम कट की क्षमता
हल किए गए उदाहरण
1. 3D ग्राफ़ पर A से BFS चलाइए (पड़ोसी वर्णमाला क्रम में)। देखने का क्रम बताइए।
कतार: A → A निकालें, B, C जोड़ें → B निकालें, D जोड़ें → C निकालें, E जोड़ें → D निकालें, F जोड़ें → E → F। क्रम: A, B, C, D, E, F। परतें: B, C 1 किनारे पर; D, E 2 पर; F 3 पर।
2. A से F तक सबसे छोटा रास्ता डाइक्स्ट्रा से निकालिए।
A 0 पक्का। B 4, C 2। C 2 पक्का; B 3 (C से), D 12, E 10। B 3 पक्का; D 8। D 8 पक्का; E 10 ही, F 14। E 10 पक्का; F 13। F 13 पक्का। रास्ता: A–C–B–D–E–F = 2 + 1 + 5 + 2 + 3 = 13 km।
3. क्रुस्कल से 3D ग्राफ़ का MST निकालिए।
क्रम: BC 1, AC 2, DE 2, EF 3, AB 4, BD 5, DF 6, CE 8, CD 10। BC, AC, DE, EF जोड़ें। AB से चक्र A-B-C बनता है: छोड़ें। BD जोड़ें। 6 शीर्षों के लिए 5 किनारे: पूरा। कुल = 1 + 2 + 2 + 3 + 5 = 13।
4. ट्री का प्री-, इन- और पोस्ट-ऑर्डर लिखिए: जड़ 8, बायाँ 3 (बच्चे 1 और 6), दायाँ 10।
प्री-ऑर्डर 8, 3, 1, 6, 10। इन-ऑर्डर 1, 3, 6, 8, 10 (बढ़ते क्रम में, क्योंकि BST है)। पोस्ट-ऑर्डर 1, 6, 3, 10, 8।
5. 3D ग्राफ़ के लिए A से शुरू और A पर ख़त्म रूट इंस्पेक्शन लंबाई निकालिए।
घातें: A2, B3, C4, D4, E3, F2। विषम: B और E। सबसे छोटा B–E: B–D–E = 7 (B–C–E = 9)। कुल भार = 41। रास्ता = 41 + 7 = 48 km; सड़कें B–D और D–E दो बार चली जाती हैं।
6. नेटवर्क: S→A 4, S→B 3, A→B 2, A→T 3, B→T 4। अधिकतम प्रवाह निकालिए और सिद्ध कीजिए।
S-A-T पर 3, S-B-T पर 3, S-A-B-T पर 1: प्रवाह = 7। S को बाक़ी से अलग करने वाले कट की क्षमता 4 + 3 = 7। प्रवाह = कट, इसलिए 7 अधिकतम है।
आम गलतियाँ
- BFS के लिए ढेर या DFS के लिए कतार लेना। BFS को कतार चाहिए; DFS को ढेर।
- डाइक्स्ट्रा में किसी शीर्ष को लेबल मिलते ही पक्का कर देना। हर बार केवल सबसे छोटा अपक्का लेबल पक्का होता है।
- क्रुस्कल में सस्ता होने के कारण चक्र बनाने वाला किनारा जोड़ देना।
- कट की क्षमता में T वाले भाग से S वाले भाग की ओर जाने वाले चाप गिन लेना। केवल S → T दिशा वाले गिनते हैं।