निर्देशित बनाम अप्रत्यक्ष ग्राफ़
एक ग्राफ एक गणितीय संरचना है जो शीर्षों और किनारों के समूह से बनी होती है। एक ग्राफ वस्तुओं के एक सेट का प्रतिनिधित्व करता है (शीर्षों द्वारा दर्शाया गया) जो कुछ लिंक (किनारों द्वारा दर्शाया गया) के माध्यम से जुड़ा हुआ है। गणितीय संकेतन का उपयोग करते हुए, एक ग्राफ को G द्वारा दर्शाया जा सकता है, जहाँ G=(V, E) और V शीर्षों का समुच्चय है और E किनारों का समुच्चय है। एक अप्रत्यक्ष ग्राफ में किनारों से जुड़ी कोई दिशा नहीं होती है जो शिखर को जोड़ती है। एक निर्देशित ग्राफ़ में किनारों से जुड़ी एक दिशा होती है जो शीर्षों को जोड़ती है।
अप्रत्यक्ष ग्राफ
जैसा कि पहले उल्लेख किया गया है, एक अप्रत्यक्ष ग्राफ एक ग्राफ है जिसमें किनारों में कोई दिशा नहीं होती है जो ग्राफ में कोने को जोड़ती है।चित्र 1 में एक अप्रत्यक्ष ग्राफ़ दिखाया गया है जिसमें शीर्षों का सेट V={V1, V2, V3} है। उपरोक्त ग्राफ में किनारों के सेट को V={(V1, V2), (V2, V3), (V1, V3)} के रूप में लिखा जा सकता है। यह भी ध्यान दिया जा सकता है कि किनारों के सेट को V={(V2, V1), (V3, V2), (V3, V1)} के रूप में लिखने से कोई रोक नहीं है क्योंकि किनारों की कोई दिशा नहीं होती है। इसलिए एक अप्रत्यक्ष ग्राफ में किनारों को जोड़े का आदेश नहीं दिया जाता है। यह एक अप्रत्यक्ष ग्राफ की मुख्य विशेषता है। अप्रत्यक्ष रेखांकन का उपयोग उन वस्तुओं के बीच सममित संबंधों का प्रतिनिधित्व करने के लिए किया जा सकता है जिन्हें शिखर द्वारा दर्शाया जाता है। उदाहरण के लिए, एक दोतरफा सड़क नेटवर्क जो शहरों के एक समूह को जोड़ता है, एक अप्रत्यक्ष ग्राफ का उपयोग करके दर्शाया जा सकता है। शहरों को ग्राफ में शीर्षों द्वारा दर्शाया जा सकता है और किनारों को शहरों को जोड़ने वाली दो-तरफा सड़कों का प्रतिनिधित्व करते हैं।
निर्देशित ग्राफ
निर्देशित ग्राफ़ एक ऐसा ग्राफ़ होता है जिसमें ग्राफ़ में किनारों को जोड़ने वाले किनारों की एक दिशा होती है। चित्र 2 में एक निर्देशित ग्राफ दिखाया गया है जिसमें शीर्षों का सेट V={V1, V2, V3} है। उपरोक्त ग्राफ में किनारों के सेट को V={(V1, V2), (V2, V3), (V1, V3)} के रूप में लिखा जा सकता है। एक अप्रत्यक्ष ग्राफ में किनारों को जोड़े का आदेश दिया जाता है। औपचारिक रूप से, एक निर्देशित ग्राफ में किनारे ई को आदेशित जोड़ी ई=(एक्स, वाई) द्वारा दर्शाया जा सकता है जहां एक्स शिखर है जिसे मूल, स्रोत या किनारे ई का प्रारंभिक बिंदु कहा जाता है, और वर्टेक्स वाई को टर्मिनस कहा जाता है, समापन शीर्ष या टर्मिनल बिंदु। उदाहरण के लिए, एक सड़क नेटवर्क जो एकतरफा सड़कों का उपयोग करके शहरों के एक समूह को जोड़ता है, एक अप्रत्यक्ष ग्राफ का उपयोग करके दर्शाया जा सकता है। शहरों को ग्राफ में शीर्षों द्वारा दर्शाया जा सकता है और निर्देशित किनारे उन सड़कों का प्रतिनिधित्व करते हैं जो शहरों को सड़क में यातायात के प्रवाह की दिशा पर विचार करते हुए जोड़ती हैं।
निर्देशित ग्राफ़ और अप्रत्यक्ष ग्राफ़ में क्या अंतर है?
निर्देशित ग्राफ़ में एक किनारा एक क्रमित युग्म होता है, जहाँ क्रमित युग्म उस किनारे की दिशा का प्रतिनिधित्व करता है जो दो शीर्षों को जोड़ता है। दूसरी ओर, एक अप्रत्यक्ष ग्राफ में, एक किनारा एक अनियंत्रित जोड़ी है, क्योंकि किनारे से जुड़ी कोई दिशा नहीं है। वस्तुओं के बीच सममित संबंधों का प्रतिनिधित्व करने के लिए अप्रत्यक्ष रेखांकन का उपयोग किया जा सकता है। अप्रत्यक्ष ग्राफ़ में प्रत्येक नोड का इन-डिग्री और आउट-डिग्री बराबर होता है लेकिन एक निर्देशित ग्राफ़ के लिए यह सच नहीं है। अप्रत्यक्ष ग्राफ का प्रतिनिधित्व करने के लिए मैट्रिक्स का उपयोग करते समय, मैट्रिक्स हमेशा एक सममित ग्राफ बन जाता है, लेकिन यह निर्देशित ग्राफ के लिए सच नहीं है। एक अप्रत्यक्ष ग्राफ को प्रत्येक किनारे को विपरीत दिशा में जाने वाले दो निर्देशित किनारों के साथ बदलकर एक निर्देशित ग्राफ में परिवर्तित किया जा सकता है। हालांकि, एक निर्देशित ग्राफ को एक अप्रत्यक्ष ग्राफ में परिवर्तित करना संभव नहीं है।
