ज़रूरी शब्द
ग्राफ़ G में शीर्षों (नोड) का समूह और किनारों (दो शीर्ष जोड़ने वाली रेखाएँ) का समूह होता है। केवल जुड़ाव मायने रखता है, चित्र कैसे बना है यह नहीं।
- आसन्न शीर्ष एक किनारे से जुड़े होते हैं।
- लूप शीर्ष को ख़ुद से जोड़ता है। बहु-किनारे एक ही जोड़े को दो बार जोड़ते हैं। सरल ग्राफ़ में दोनों नहीं।
- दिष्ट ग्राफ़ में एक-तरफ़ा तीर होते हैं, जैसे वन-वे सड़कें।
- भारित ग्राफ़ में हर किनारे पर संख्या होती है: दूरी, समय या लागत।
- आसन्नता आव्यूह एक सारणी है: पंक्ति A, स्तंभ B में A से B के किनारों की संख्या।
घात और हाथ मिलाने का नियम
शीर्ष v की घात deg(v) उस पर मिलने वाले किनारों के सिरों की संख्या है (लूप 2 गिना जाता है)।
हाथ मिलाने का नियम (Handshake lemma): सभी घातों का योग = 2 × किनारों की संख्या। हर किनारे के दो सिरे हैं, इसलिए वह योग में 2 जोड़ता है।
इसलिए कुल घात हमेशा सम है, और विषम घात वाले शीर्षों की संख्या हमेशा सम होती है।
उदाहरण: 6 लोगों की पार्टी में हर कोई हर किसी से हाथ मिलाए तो हर एक की घात 5। योग = 30, यानी 15 हाथ मिलाना।
पथ, चक्र, ऑयलर और हैमिल्टन
भ्रमण (walk) किनारों पर चलना है। ट्रेल में कोई किनारा दोहराया नहीं जाता। पथ में कोई शीर्ष नहीं दोहराया जाता। चक्र वह पथ है जो शुरुआत पर लौटे। ग्राफ़ संबद्ध है अगर किसी भी शीर्ष से किसी भी शीर्ष तक जा सकें।
ऑयलर (1736) ने कोनिग्सबर्ग के 7 पुलों की पहेली हल की। संबद्ध ग्राफ़ में:
- सारी घातें सम हों तो ऑयलर परिपथ (हर किनारा एक बार, शुरुआत पर वापस);
- ठीक 2 विषम हों तो ऑयलर पथ: एक से शुरू, दूसरे पर ख़त्म;
- 2 से ज़्यादा विषम हों तो कोई नहीं।
हैमिल्टन चक्र हर शीर्ष पर एक बार जाकर लौटता है। इसकी कोई आसान जाँच नहीं; खोजना पड़ता है।
यादृच्छिक भ्रमण में हर चरण पर किसी पड़ोसी पर संयोग से जाते हैं। इसका लंबा व्यवहार आव्यूहों (मार्कोव शृंखला) से समझा जाता है; शुरुआती वेब सर्च ने पेज इसी तरह क्रमित किए।
विशेष ग्राफ़, वृक्ष, समतलीयता और विस्तृत वृक्ष
- पूर्ण ग्राफ़ Kₙ: हर जोड़ा जुड़ा; n(n − 1)/2 किनारे।
- द्विभाजित ग्राफ़: शीर्ष दो समूहों में, किनारे केवल समूहों के बीच।
- वृक्ष: संबद्ध और बिना चक्र। n शीर्षों के वृक्ष में ठीक n − 1 किनारे। वंश-वृक्ष और कंप्यूटर के फ़ोल्डर वृक्ष हैं।
तुल्याकारी (isomorphic) ग्राफ़ एक ही ग्राफ़ हैं, बस अलग ढंग से बने। जल्दी जाँच: शीर्ष, किनारे और घातों की सूची समान हो।
समतलीय ग्राफ़ बिना किनारे काटे बन सकता है। संबद्ध समतलीय ग्राफ़ के लिए ऑयलर सूत्र: V − E + F = 2 (F में बाहर का क्षेत्र भी)। K₅ और K₃,₃ समतलीय नहीं।
विस्तृत वृक्ष सभी शीर्ष बिना चक्र के जोड़ता है। न्यूनतम विस्तृत वृक्ष का कुल भार सबसे कम। क्रुस्कल: किनारे भार के क्रम में, सबसे सस्ता जो चक्र न बनाए। प्रिम: एक शीर्ष से बढ़ते हुए नए शीर्ष तक सबसे सस्ता किनारा। डाइकस्ट्रा एक शीर्ष से सबसे छोटे पथ ढूँढता है।
मुख्य सूत्र और परिभाषाएँ
- Σ deg(v) = 2E (हाथ मिलाने का नियम)
- पूर्ण ग्राफ़ Kₙ में किनारे = n(n − 1)/2
- n शीर्षों के वृक्ष में किनारे = n − 1
- संबद्ध समतलीय ग्राफ़ के लिए ऑयलर सूत्र: V − E + F = 2
- ऑयलर परिपथ: सभी घात सम; ऑयलर पथ: ठीक 2 विषम शीर्ष
- सरल समतलीय ग्राफ़ (V ≥ 3): E ≤ 3V − 6
हल किए गए उदाहरण
1. एक ग्राफ़ की घातें 3, 3, 2, 2, 2 हैं। कितने किनारे?
योग = 12। किनारे = 12 ÷ 2 = 6।
2. K₇ में कितने किनारे हैं?
7 × 6 ÷ 2 = 21।
3. क्या घातें 3, 3, 3, 2 वाला ग्राफ़ संभव है?
योग = 11, विषम। योग 2E यानी सम होना चाहिए, इसलिए असंभव।
4. संबद्ध ग्राफ़ की घातें A 2, B 4, C 3, D 2, E 3। ऑयलर परिपथ या पथ?
विषम शीर्ष: C और E, ठीक 2। इसलिए C से E तक ऑयलर पथ है, परिपथ नहीं।
5. संबद्ध समतलीय ग्राफ़ में 8 शीर्ष और 12 किनारे हैं। कितने क्षेत्र?
8 − 12 + F = 2 → F = 6।
6. किनारे: AB 4, BC 3, CD 5, DE 2, EA 6, AC 7, BD 4, BE 8। क्रुस्कल से न्यूनतम विस्तृत वृक्ष ज्ञात कीजिए।
क्रम: DE 2, BC 3, AB 4, BD 4, CD 5 … DE, BC, AB, BD लिए; अब 5 शीर्ष 4 किनारों से जुड़े। CD चक्र बनाता। कुल = 13 km।
आम गलतियाँ
- लूप की घात 1 गिनना। लूप शीर्ष को दो बार छूता है, 2 जुड़ता है।
- ऑयलर (हर किनारा एक बार) और हैमिल्टन (हर शीर्ष एक बार) को मिलाना।
- ऑयलर नियम लगाने से पहले यह न देखना कि ग्राफ़ संबद्ध है।
- ऑयलर सूत्र में बाहर का क्षेत्र गिनना भूल जाना।