ग्राफ सिद्धांत
“एक ग्राफ एक ऐसा नक्शा है जो स्थान छोड़कर केवल संबंध रखता है।”
सूत्र
G = (V, E), Σ(v∈V) deg(v) = 2|E|कैसे पढ़ें: एक ग्राफ शीर्षों का समुच्चय V और उन्हें जोड़ने वाले किनारों का समुच्चय E है; हर शीर्ष की घात जोड़ने पर किनारों की संख्या का दोगुना मिलता है
- V
- — शीर्षों का समुच्चय—'बिंदु'
- E
- — किनारों का समुच्चय—बिंदुओं को जोड़ने वाली 'रेखाएं'
- deg(v)
- — v की घात—उससे जुड़े किनारों की संख्या
- Σdeg(v) = 2|E|
- — घातों का योग किनारों की संख्या का दोगुना होता है (हैंडशेक लेम्मा)
शुरुआत
दोस्ती, मेट्रो के नक्शे, इंटरनेट, अणु—इन सबको एक सरल तस्वीर से पकड़ा जा सकता है: बिंदु और रेखाएं।
सरल शब्दों में
एक ग्राफ बिंदुओं (शीर्षों) और उन्हें जोड़ने वाली रेखाओं (किनारों) का संग्रह है। यह केवल यह दर्ज करता है कि क्या किससे जुड़ा है, स्थिति, आकार और दूरी को छोड़ देता है। यह संबंधों का एक ऐसा नक्शा है जो केवल ढांचे तक सिमटा हुआ है।
अंतर्ज्ञान
एक मेट्रो के नक्शे की कल्पना करें—असल दूरियां और दिशाएं गलत हैं, लेकिन 'कौन-सा स्टेशन किससे जुड़ा है' पूरी तरह सुरक्षित रहता है। यही ग्राफ की भावना है। चाहे बिंदु कुछ भी हों (लोग, शहर, वेब पेज) और रेखाएं कुछ भी हों (दोस्ती, सड़कें, लिंक), केवल संबंध की संरचना देखने से बहुत अलग समस्याएं एक ही समस्या बन जाती हैं।
कैसे बनता है
दो हिस्से—एक शीर्ष समुच्चय V और एक किनारा समुच्चय E। हर शीर्ष की 'घात' उससे जुड़े किनारों की संख्या है। हैंडशेक लेम्मा: सभी घातों को जोड़ने पर ठीक-ठीक किनारों की संख्या का दोगुना मिलता है (हर किनारा अपने दोनों सिरों पर एक-एक बार गिना जाता है)। यह सरल गिनती आश्चर्यजनक रूप से शक्तिशाली है।
उदाहरण
एक त्रिभुज ग्राफ: 3 शीर्ष, 3 किनारे। हर शीर्ष की घात 2 है, तो घातों का योग 2+2+2 = 6 = 2 × 3 (किनारों की संख्या)। हैंडशेक लेम्मा ठीक-ठीक सही बैठता है।
आम ग़लतफ़हमी
यहां 'ग्राफ' फलन y=f(x) का वक्र नहीं है। यहां कोई अक्ष नहीं, कोई वक्र नहीं—केवल बिंदुओं का एक नेटवर्क और उन्हें जोड़ने वाली रेखाएं हैं। एक ही शब्द, बिल्कुल अलग वस्तु।
कहाँ उपयोग होता है
गूगल की खोज रैंकिंग (पेजरैंक), GPS की सबसे छोटी राह, सामाजिक-नेटवर्क विश्लेषण, परिपथ डिज़ाइन, शेड्यूलिंग और रंगीकरण समस्याएं, महामारी-प्रसार मॉडल—हर समस्या जहां चीज़ें चीज़ों से जुड़ी हों, वह एक ग्राफ है।
कहाँ से आया
1736 में ऑयलर ने यह पहेली हल की कि क्या कोएनिग्सबर्ग के सातों पुलों को ठीक एक बार पार किया जा सकता है, जिसने ग्राफ सिद्धांत और सांस्थिति (टोपोलॉजी) के द्वार खोल दिए (जवाब: असंभव)।
पूर्वापेक्षाएँ
त्वरित जाँच
हैंडशेक लेम्मा के अनुसार, 5 किनारों वाले ग्राफ में सभी शीर्ष घातों का योग क्या है?
- 5
- 10✓
- 25
- 2.5
अभ्यास
4 किनारों वाले ग्राफ में सभी शीर्ष घातों का योग ज्ञात करें।
उत्तर: 8
- हैंडशेक लेम्मा: घातों का योग = 2 × किनारों की संख्या
- = 2 × 4 = 8
मुख्य बात: हर किनारा कुल घात में 2 जोड़ता है।
पूर्ण ग्राफ K₄ (4 शीर्ष, हर जोड़ा जुड़ा हुआ) में किनारों की संख्या ज्ञात करें।
उत्तर: 6
- 4 में से 2 शीर्ष चुनने के तरीके, C(4,2)
- = (4·3)/2 = 6
मुख्य बात: पूर्ण ग्राफ Kₙ में n(n−1)/2 किनारे होते हैं।
एक ग्राफ में शीर्षों की घात 3, 3, 2, 2 है। इसके किनारों की संख्या ज्ञात करें।
उत्तर: 5
- घातों का योग = 3+3+2+2 = 10
- किनारे = 10 / 2 = 5
मुख्य बात: किनारों की संख्या घातों के योग का आधा है।
घातों का उपयोग करके समझाएं कि कोई भी यात्रा कोएनिग्सबर्ग के सातों पुलों को ठीक एक बार पार क्यों नहीं कर सकती।
उत्तर: undefined
- ऐसी यात्रा (यूलर पथ) को 0 या 2 विषम-घात शीर्षों की ज़रूरत होती है
- कोएनिग्सबर्ग में सभी चार भूभागों की घात विषम है
- चार विषम-घात शीर्ष (2 से अधिक) इसे असंभव बना देते हैं
मुख्य बात: तीन या अधिक विषम-घात शीर्षों का मतलब है कोई यूलर पथ नहीं है।