ग्राफ़ थ्योरी

बिंदु और उनके बीच की रेखाएँ: ग्राफ़ बस इतना ही है। फिर भी यही तस्वीर सड़कों के नक्शे, दोस्तों के नेटवर्क, किसी अणु और इंटरनेट को दर्शाती है, और इसके बारे में पूछे जा सकने वाले सवालों ने, इसे कितने रंग चाहिए से लेकर क्या इसे बिना पेन उठाए बनाया जा सकता है तक, 1736 से गणितज्ञों को व्यस्त रखा है।

दस वर्टेक्स वाला एक ग्राफ़, पीटरसन ग्राफ़, जिसके वर्टेक्स तीन रंगों में इस तरह रंगे हैं कि कोई एज एक ही रंग के दो वर्टेक्स को नहीं जोड़ता
दस वर्टेक्स वाला एक ग्राफ़, पीटरसन ग्राफ़, जिसके वर्टेक्स तीन रंगों में इस तरह रंगे हैं कि कोई एज एक ही रंग के दो वर्टेक्स को नहीं जोड़ता

वर्टेक्स और एज

ग्राफ़ में वर्टेक्स होते हैं, जिन्हें नोड भी कहते हैं, और एज, जिनमें से हर एक दो वर्टेक्स को जोड़ता है। वर्टेक्स कहाँ बनाए गए हैं, इससे फ़र्क नहीं पड़ता, सिर्फ़ इससे पड़ता है कि कौन-से जोड़े जुड़े हैं, इसलिए एक ही ग्राफ़ कागज़ पर बिल्कुल अलग दिख सकता है। प्लेग्राउंड के ग्राफ़ सरल होते हैं: किसी वर्टेक्स से खुद तक कोई एज नहीं, और दो वर्टेक्स के बीच ज़्यादा से ज़्यादा एक एज। n वर्टेक्स के साथ ज़्यादा से ज़्यादा n(n − 1) / 2 एज हो सकते हैं; जिस ग्राफ़ में ये सब हों, उसे पूर्ण ग्राफ़ कहते हैं, और K5 पाँच वर्टेक्स वाला पूर्ण ग्राफ़ है।

डिग्री और हैंडशेक लेम्मा

किसी वर्टेक्स की डिग्री उससे जुड़े एजों की संख्या है। सभी डिग्रियों को जोड़ें तो ठीक एजों की संख्या का दोगुना मिलता है, क्योंकि हर एज के दो सिरे होते हैं और वह हर सिरे पर एक बार गिना जाता है। यही हैंडशेक लेम्मा है: किसी भी समूह में, हर व्यक्ति के हिसाब से गिने गए हाथ मिलाने का कुल जोड़ हाथ मिलाने की संख्या का दोगुना होता है। इसका यह भी मतलब है कि विषम डिग्री वाले वर्टेक्स की संख्या हमेशा सम होती है। जिस ग्राफ़ में हर वर्टेक्स की डिग्री एक ही k हो, उसे k-रेगुलर कहते हैं।

कनेक्टेड ग्राफ़, ट्री और साइकिल

ग्राफ़ कनेक्टेड तब होता है जब आप एजों के सहारे हर वर्टेक्स से हर दूसरे वर्टेक्स तक जा सकें; नहीं तो वह टुकड़ों में बँट जाता है, जिन्हें कंपोनेंट कहते हैं। साइकिल एक ऐसा चक्कर है जो किसी वर्टेक्स को दो बार इस्तेमाल किए बिना अपनी शुरुआत पर लौट आता है, और सबसे छोटे साइकिल की लंबाई गर्थ कहलाती है। बिना साइकिल वाला कनेक्टेड ग्राफ़ ट्री होता है, और n वर्टेक्स वाले ट्री में हमेशा ठीक n − 1 एज होते हैं: एक कम हो तो वह बिखर जाता है, एक ज़्यादा हो तो उसमें साइकिल बन जाता है। हर कनेक्टेड ग्राफ़ में एक स्पैनिंग ट्री होता है, यानी ऐसा ट्री जो सिर्फ़ कुछ एजों के सहारे हर वर्टेक्स तक पहुँचता है।

बाइपार्टाइट ग्राफ़ और कलरिंग

वर्टेक्स को इस तरह रंगें कि कोई एज एक ही रंग के दो वर्टेक्स को न जोड़े। ऐसा करने के लिए ज़रूरी रंगों की न्यूनतम संख्या क्रोमैटिक संख्या है। एक रंग तभी काफ़ी है जब कोई एज न हो। दो रंग ठीक तब काफ़ी हैं जब ग्राफ़ बाइपार्टाइट हो: उसके वर्टेक्स दो पक्षों में बँटें और हर एज एक पक्ष से दूसरे तक जाए। डेनेश कोनिग ने 1936 में दिखाया कि यह विषम लंबाई का कोई साइकिल न होने के बराबर है, क्योंकि विषम साइकिल में दो रंग बारी-बारी से नहीं आ सकते। तीन या ज़्यादा रंगों के लिए ऐसी कोई सरल जाँच ज्ञात नहीं है: तीन रंग काफ़ी हैं या नहीं, यह तय करना NP-complete है, इसलिए प्रोग्राम सर्च करते हैं, जैसा प्लेग्राउंड करता है।

एक उदाहरण: पीटरसन ग्राफ़

एक पंचभुज A–B–C–D–E लें और उसके अंदर पाँच कोनों वाला एक तारा F–H–J–G–I, और पंचभुज के हर कोने को तारे के एक कोने से जोड़ें: A–F, B–G, C–H, D–I और E–J। यही पीटरसन ग्राफ़ है, जिसमें 10 वर्टेक्स और 15 एज हैं। हर वर्टेक्स की डिग्री 3 है, इसलिए डिग्रियों का योग 30 है, यानी 15 का दोगुना। इसके सबसे छोटे साइकिल की लंबाई 5 है, इसलिए इसमें कोई त्रिभुज नहीं है, लेकिन पंचभुज एक विषम साइकिल है, इसलिए यह बाइपार्टाइट नहीं है और इसे 3 रंग चाहिए। कोई भी दो वर्टेक्स ज़्यादा से ज़्यादा 2 एज दूर हैं, इसलिए इसका व्यास 2 है। सभी दस डिग्रियाँ विषम हैं, इसलिए इसमें कोई यूलर ट्रेल नहीं है, और इसे क्रॉसिंग के बिना नहीं बनाया जा सकता।

यूलर पाथ और कोनिग्सबर्ग के पुल

कोनिग्सबर्ग शहर में सात पुल ज़मीन के चार हिस्सों को जोड़ते थे, और लोग पूछते थे कि क्या हर पुल को ठीक एक बार पार करते हुए घूमा जा सकता है। 1736 में लियोनहार्ड यूलर ने दिखाया कि ऐसा नहीं हो सकता, और यहीं से ग्राफ़ थ्योरी की शुरुआत हुई। सैर जब भी ज़मीन के किसी हिस्से से होकर गुज़रती है, दो पुल इस्तेमाल करती है, इसलिए सिर्फ़ शुरुआत और अंत वाले हिस्सों से जुड़े पुलों की संख्या विषम हो सकती है, जबकि कोनिग्सबर्ग के चारों हिस्सों से जुड़े पुलों की संख्या विषम थी। हर एज का एक बार इस्तेमाल करने वाले ट्रेल को अब यूलर पाथ कहते हैं, या यूलर सर्किट, अगर वह वहीं खत्म हो जहाँ से शुरू हुआ था। कार्ल हीरहोल्ज़र ने 1873 में साबित किया कि यह शर्त काफ़ी भी है: अगर सारे एज एक ही टुकड़े में हों और ज़्यादा से ज़्यादा दो डिग्री विषम हों, तो ट्रेल मौजूद होता है, और चक्करों को आपस में जोड़ने का उनका तरीका आज भी उसे खोज लेता है।

कोनिग्सबर्ग (Koningsberga) का ऐतिहासिक पक्षी-दृष्टि मानचित्र, प्रेगेल नदी और सात पुलों की समस्या के केंद्र में स्थित द्वीप दिखाता है। 1736 में लियोनहार्ड ऑयलर ने दिखाया कि कोई सैर प्रत्येक पुल को ठीक एक बार पार नहीं कर सकती, और ग्राफ़ सिद्धांत आरंभ हुआ।
कोनिग्सबर्ग (Koningsberga) का ऐतिहासिक पक्षी-दृष्टि मानचित्र, प्रेगेल नदी और सात पुलों की समस्या के केंद्र में स्थित द्वीप दिखाता है। 1736 में लियोनहार्ड ऑयलर ने दिखाया कि कोई सैर प्रत्येक पुल को ठीक एक बार पार नहीं कर सकती, और ग्राफ़ सिद्धांत आरंभ हुआ।
लियोनहार्ड यूलर का चित्र
लियोनहार्ड यूलर का चित्र

दूरी, व्यास और पूरक

दो वर्टेक्स के बीच की दूरी उनके बीच के किसी पाथ पर एजों की न्यूनतम संख्या है, और व्यास ग्राफ़ की सबसे बड़ी दूरी है; जो ग्राफ़ कनेक्टेड नहीं है, उसमें यह अनंत होता है। सोशल नेटवर्क के व्यास छोटे होते हैं, “सिक्स डिग्रीज़ ऑफ़ सेपरेशन” के पीछे यही विचार है। किसी ग्राफ़ के पूरक में वही वर्टेक्स होते हैं और वह ठीक उन जोड़ों को जोड़ता है जो जुड़े नहीं थे। किसी ग्राफ़ और उसके पूरक में से कम से कम एक हमेशा कनेक्टेड होता है।

खुद आज़माएँ

प्लेग्राउंड तीन रंगों में रंगे पीटरसन ग्राफ़ के साथ खुलता है। “डिग्री” पर क्लिक करें और हैंडशेक लेम्मा जाँचें, विषम साइकिल देखने के लिए “बाइपार्टाइट” पर क्लिक करें, फिर घन लोड करें और दोनों पक्षों को उभरते देखें। घर लोड करें और “यूलर ट्रेल” पर क्लिक करके देखें कि बिना पेन उठाए रेखा कहाँ से शुरू करनी होगी। अपना ग्राफ़ बनाएँ और एक-एक करके एज जोड़ें: देखें कि सबसे छोटा साइकिल कैसे छोटा होता है, व्यास कैसे घटता है, और K4 का आखिरी एज जुड़ते ही क्रोमैटिक संख्या कैसे बढ़ जाती है।

अक्सर पूछे जाने वाले प्रश्न

पाथ, ट्रेल और वॉक में क्या अंतर है?

वॉक एजों से जुड़े वर्टेक्स का कोई भी क्रम है, और इसमें वर्टेक्स और एज दोनों दोहराए जा सकते हैं। ट्रेल में वर्टेक्स दोहराए जा सकते हैं, एज नहीं, इसीलिए यूलर ट्रेल किसी वर्टेक्स से कई बार गुज़र सकता है। पाथ में दोनों में से कुछ भी नहीं दोहराया जाता।

चार रंग प्रमेय क्या है?

यह कहता है कि जिस भी ग्राफ़ को कागज़ पर एजों को काटे बिना बनाया जा सकता है, उसे ज़्यादा से ज़्यादा चार रंगों से रंगा जा सकता है, इसलिए किसी भी नक्शे के लिए चार से ज़्यादा रंग नहीं चाहिए। इसे 1976 में केनेथ अपेल और वोल्फ़गैंग हाकेन ने कंप्यूटर की मदद से साबित किया, और यह इस तरह साबित होने वाला पहला बड़ा प्रमेय था।

हैमिल्टोनियन साइकिल क्या है?

ऐसा साइकिल जो हर एज के बजाय हर वर्टेक्स से ठीक एक बार गुज़रता है। यह यूलर वाले सवाल जैसा लगता है, लेकिन इसके लिए कोई सरल जाँच ज्ञात नहीं है: किसी ग्राफ़ में ऐसा साइकिल है या नहीं, यह तय करना NP-complete है। पीटरसन ग्राफ़ में हैमिल्टोनियन पाथ है, लेकिन हैमिल्टोनियन साइकिल नहीं।

ग्राफ़ थ्योरी का इस्तेमाल कहाँ होता है?

रूट प्लानर सड़कों के ग्राफ़ में सर्च करते हैं, सर्च इंजन वेब पेजों को उनके लिंक के आधार पर रैंक करते हैं, कंपाइलर प्रोसेसर रजिस्टर बाँटने के लिए ग्राफ़ कलरिंग करते हैं, टाइमटेबल टकरावों के ग्राफ़ को रंगकर टकराव से बचते हैं, रसायनशास्त्री अणुओं को ग्राफ़ मानकर गिनते हैं, और कंप्यूटरों, बिजली की लाइनों और दोस्तों के नेटवर्क का अध्ययन ग्राफ़ के रूप में किया जाता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

ग्राफ़ थ्योरी प्लेग्राउंड खोलें