ग्राफ़ सिद्धांत का परिचय

आप वस्तुओं के बीच द्वयीय (pairwise) संबंधों का मॉडल कैसे बनाते हैं? 

एक गणितीय संरचना जिसे ग्राफ़ कहते हैं, से। और यही ग्राफ़ सिद्धांत का सार है – ग्राफ़ का अध्ययन।  

ग्राफ़ सिद्धांत के मूल तत्व वर्टिसेज़ (जिन्हें नोड्स भी कहा जाता है) और एजेज़ (जिन्हें लिंक्स भी कहा जाता है) हैं। एक वर्टेक्स ग्राफ़ के भीतर किसी इकाई या बिंदु का प्रतिनिधित्व करता है, जबकि एक एज दो वर्टिसेज़ के बीच कनेक्शन या संबंध को दर्शाता है। साथ मिलकर, ये घटक ग्राफ़ की संरचना बनाते हैं, जो निर्देशित या अनिर्देशित, वेटेड या अनवेटेड हो सकती है, यह इस पर निर्भर करता है कि मॉडल किए जा रहे संबंधों की प्रकृति क्या है।

कंप्यूटर विज्ञान में, ग्राफ़ सिद्धांत कई एल्गोरिदम और डेटा संरचनाओं की बुनियाद है, जिनका उपयोग इंटरनेट, सोशल नेटवर्क्स और संचार प्रणालियों जैसे नेटवर्क का प्रतिनिधित्व करने के लिए किया जाता है। यह नेटवर्क कनेक्टिविटी, पाथफाइंडिंग और ऑप्टिमाइज़ेशन से संबंधित समस्याओं को हल करने के उपकरण भी प्रदान करता है, और पेड़ों (trees), साइकिल्स और प्लानर ग्राफ़ जैसे विभिन्न गणितीय ढाँचों और अवधारणाओं को समझने के लिए बुनियादी है।

इस लेख में, हम आपको ग्राफ़ सिद्धांत शुरू करने के लिए आवश्यक जानकारियाँ सिखाएँगे।  

लेखक द्वारा Midjourney का उपयोग कर बनाया गया

ग्राफ़ सिद्धांत क्या है?

ग्राफ़ सिद्धांत गणित की वह शाखा है जो ग्राफ़ के गुणों और अनुप्रयोगों का अध्ययन करती है। एक ग्राफ़ वर्टिसेज़ (या नोड्स) नामक वस्तुओं के समूह को परिभाषित करता है, जिन्हें एजेज़ (या लिंक्स) द्वारा जोड़ा जाता है। 

ग्राफ़ सिद्धांत का प्राथमिक लक्ष्य इन ग्राफ़ों की संरचना को समझना और कनेक्टिविटी, पाथफाइंडिंग और नेटवर्क ऑप्टिमाइज़ेशन से संबंधित विभिन्न समस्याओं का अन्वेषण करना है।

इन संबंधों का विश्लेषण करके, ग्राफ़ सिद्धांत हमें कई क्षेत्रों में असंख्य वास्तविक दुनिया की समस्याओं पर अंतर्दृष्टि प्राप्त करने में सक्षम बनाता है।

ग्राफ़ सिद्धांत कहाँ से आया?

ग्राफ़ सिद्धांत की उत्पत्ति 18वीं शताब्दी में स्विस गणितज्ञ लियोनहार्ड ऑयलर के कार्य से हुई। 1736 में क्योनिग्सबर्ग ब्रिज समस्या का ऑयलर का समाधान ग्राफ़ सिद्धांत की पहली समस्याओं में से एक माना जाता है। इस समस्या में क्योनिग्सबर्ग शहर में ऐसा पैदल मार्ग खोजने की बात थी जो उसकी सातों पुलों को ठीक एक बार पार करे। ऑयलर के दृष्टिकोण ने आगे चलकर ग्राफ़ के औपचारिक अध्ययन की नींव रखी।

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

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

ग्राफ़ सिद्धांत की बुनियादी अवधारणाएँ

ग्राफ़ सिद्धांत की बुनियादी बातों को समझना, इस क्षेत्र के उन्नत विषयों का अन्वेषण करने का आधार प्रदान करता है। तो शुरू करने के लिए, आइए कुछ नींव रखते हैं… 

क्रमबद्ध युग्म (Ordered Pairs) के रूप में ग्राफ़

एक ग्राफ़ औपचारिक रूप से एक क्रमबद्ध युग्म G = (V, E) के रूप में परिभाषित होता है, जहाँ:

• V वर्टिसेज़ (या नोड्स) का समुच्चय है, जो ग्राफ़ में व्यक्तिगत इकाइयों का प्रतिनिधित्व करता है।
• E एजेज़ (या लिंक्स) का समुच्चय है, जो वर्टिसेज़ के युग्मों के बीच कनेक्शन का प्रतिनिधित्व करता है।

वर्टिसेज़ (V) और एजेज़ (E)

• वर्टिसेज़ (V): ये ग्राफ़ की मूल इकाइयाँ या बिंदु होते हैं। प्रत्येक वर्टेक्स मॉडल की जा रही संरचना में एक इकाई या स्थान का प्रतिनिधित्व करता है।

• एजेज़ (E): ये वर्टिसेज़ के युग्मों के बीच कनेक्शन या संबंध होते हैं। प्रत्येक एज दो वर्टिसेज़ को जोड़ता है, जो उनके बीच संबंध या पथ को दर्शाता है।

एज के प्रकार

• डायरेक्टेड एजेज़: निर्देशित ग्राफ़ (या डाइग्राफ़) में, एजेज़ की दिशा होती है, अर्थात वे एक वर्टेक्स से किसी विशिष्ट दूसरे वर्टेक्स तक जाते हैं। यह दिशा अक्सर तीर से दर्शाई जाती है। निर्देशित एजेज़ विषम (asymmetric) संबंधों का मॉडल बनाने में सहायक होते हैं, जैसे ट्रैफ़िक का प्रवाह या शेड्यूलिंग में प्रीसिडेंस बाधाएँ।

• अनडायरेक्टेड एजेज़: अनिर्देशित ग्राफ़ में, एजेज़ की कोई दिशा नहीं होती और वे केवल दो वर्टिसेज़ को जोड़ते हैं। इस प्रकार का ग्राफ़ सममित संबंधों को दर्शाने के लिए उपयोग होता है, जैसे पारस्परिक मित्रता या ऐसे नेटवर्क कनेक्शन जहाँ दिशा का महत्व नहीं है।

ग्राफ़ सिद्धांत की बुनियादी शब्दावली और अवधारणाएँ

अब, आइए कुछ बुनियादी शब्द और अवधारणाएँ परिभाषित करें: 

वर्टेक्स (नोड)

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

किसी वर्टेक्स की डिग्री

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

पाथ (मार्ग)

ग्राफ़ में पाथ वर्टिसेज़ का एक अनुक्रम है, जहाँ प्रत्येक सटे हुए युग्म को एक एज जोड़ता है। ये सरल (बिना दोहराव वाले वर्टेक्स) या सामान्य (दोहराव की अनुमति) हो सकते हैं। उदाहरण के लिए, A, B, C और D वर्टिसेज़ वाले एक ग्राफ़ में, एक पाथ A → B → C → D हो सकता है, जहाँ प्रत्येक वर्टेक्स अगले से एक एज द्वारा जुड़ा है।

साइकिल

साइकिल वह पाथ है जो उसी वर्टेक्स पर शुरू होकर उसी पर समाप्त होता है, बिना अन्य वर्टिसेज़ या एजेज़ को दोहराए। साइकिल्स सरल (आरंभ और अंत के अलावा कोई पुनरावृत्ति नहीं) या सामान्य हो सकते हैं। उदाहरण: A, B, C और D वर्टिसेज़ वाले ग्राफ़ में, एक सरल साइकिल A → B → C → D → A हो सकती है।

कनेक्टेड ग्राफ़

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

ग्राफ़ के प्रकार

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

सिंपल ग्राफ़

सिंपल ग्राफ़ का चित्रण स्रोत: Wikipedia

सिंपल ग्राफ़ वह ग्राफ़ है जिसमें एक ही वर्टेक्स-युग्म के बीच एक से अधिक एज (मल्टिपल एज) नहीं होते और न ही लूप्स (ऐसे एज जो किसी वर्टेक्स को उसी से जोड़ते हों) होते हैं। सिंपल ग्राफ़ में प्रत्येक एज दो भिन्न वर्टिसेज़ को जोड़ता है।

उदाहरण:

• एक बुनियादी सोशल नेटवर्क जहाँ प्रत्येक मित्रता दो लोगों के बीच एकल लिंक से प्रदर्शित होती है।
• शहरों का मानचित्र जहाँ उन्हें एकल, प्रत्यक्ष सड़कों से जोड़ा गया है, बिना बहु मार्गों या स्व-सम्बंधों के।

मल्टीग्राफ़

मल्टीग्राफ़ का चित्रण जिसमें लाल रंग में मल्टिपल एज और नीले रंग में कई लूप्स दिखाए गए हैं स्रोत: Wikipedia

मल्टीग्राफ़ में एक ही वर्टेक्स-युग्म के बीच कई एज (समानांतर एज) की अनुमति होती है और इसमें लूप्स भी हो सकते हैं। इस प्रकार का ग्राफ़ ऐसी स्थितियों का प्रतिनिधित्व कर सकता है जहाँ संस्थाओं के बीच कई अंतःक्रियाएँ या कनेक्शन मौजूद हों।

उदाहरण:

• एक परिवहन नेटवर्क जहाँ कई एयरलाइंस एक ही शहरों के बीच उड़ानें संचालित करती हैं।
• एक संचार नेटवर्क जिसमें एक ही संचार नोड-युग्म को जोड़ने वाले कई चैनल होते हैं।

वेटेड ग्राफ़

वेटेड ग्राफ़ का चित्रण स्रोत: Hyperskill

वेटेड ग्राफ़ में, प्रत्येक एज के साथ कोई भार या लागत जुड़ी होती है, जो दूरी, समय या क्षमता जैसी मात्रात्मक माप का प्रतिनिधित्व करती है। वेटेड ग्राफ़ का उपयोग उन समस्याओं के मॉडल के लिए होता है जहाँ एजेज़ की ताकत या लागतें अलग-अलग होती हैं।

अनुप्रयोग:

• सड़कों से जुड़े शहरों के मानचित्र में, भार शहरों के बीच की दूरी या यात्रा समय दर्शा सकते हैं।
• नेटवर्क ऑप्टिमाइज़ेशन समस्याओं में, भार संचार लिंक्स की बैंडविड्थ या लागत का प्रतिनिधित्व कर सकते हैं।

डायरेक्टेड ग्राफ़ (डाइग्राफ़)

डायरेक्टेड ग्राफ़ का चित्रण स्रोत: Wikipedia

डायरेक्टेड ग्राफ़, या डाइग्राफ़, में एजेज़ की एक विशिष्ट दिशा होती है, अर्थात प्रत्येक एज एक वर्टेक्स से किसी दूसरे भिन्न वर्टेक्स तक जाता है। दिशा अक्सर तीर द्वारा दर्शाई जाती है, जो प्रवाह या एक-तरफ़ा संबंध को इंगित करती है।

उपयोग के मामले:

• वर्कफ़्लो आरेख जहाँ कार्यों को एक विशिष्ट क्रम में पूरा करना होता है।
• वेब पेज लिंकिंग संरचना, जहाँ हाइपरलिंक्स एक पेज से दूसरे की ओर इशारा करते हैं, जो एक-तरफ़ा कनेक्शन का प्रतिनिधित्व करता है।

अनडायरेक्टेड ग्राफ़

अनडायरेक्टेड ग्राफ़ का चित्रण स्रोत: Baeldung

अनिर्देशित ग्राफ़ में, एजेज़ की कोई दिशा नहीं होती। एक एज मात्र दो वर्टिसेज़ को जोड़ती है, और संबंध पारस्परिक या द्वि-दिशात्मक होता है। एज में वर्टिसेज़ का क्रम मायने नहीं रखता।

उदाहरण:

• मित्रों का नेटवर्क जहाँ मित्रता पारस्परिक है, और कनेक्शन द्वि-दिशात्मक हैं।
• एक अनिर्देशित रोड मैप जहाँ सड़कें शहरों को दोनों दिशाओं में जोड़ती हैं, बिना दिशा निर्दिष्ट किए।

ट्री ग्राफ़ सिद्धांत

ट्री एक ऐसा ग्राफ़ है जो कनेक्टेड और ए-साइक्लिक (चक्र-रहित) होता है, यानी इसमें कोई साइकिल नहीं होती। $$n$$ वर्टिसेज़ वाले ट्री में ठीक $$n−1$$ एजेज़ होते हैं। ट्री में हर वर्टेक्स-युग्म के बीच ठीक एक पाथ होता है, जो यह सुनिश्चित करता है कि किसी भी दो वर्टिसेज़ के बीच एक अद्वितीय पाथ मौजूद है।

यहाँ ट्री ग्राफ़ के गुणों का एक त्वरित सारांश है: 

• कनेक्टेड. किसी भी वर्टेक्स-युग्म के बीच एक पाथ मौजूद है।
• ए-साइक्लिक. कोई साइकिल नहीं होती, जिससे बंद लूप्स नहीं बनते।
• अद्वितीय पाथ. किसी भी दो वर्टिसेज़ के बीच ठीक एक पाथ होता है, जो इंगित करता है कि ग्राफ़ न्यूनतम रूप से कनेक्टेड है।
• एजों की संख्या. $$n$$ वर्टिसेज़ वाले ट्री में $$n−1$$ एजेज़ होते हैं।
• सबट्री: ट्री का कोई भी उपसमुच्चय, एकल वर्टेक्स सहित, स्वयं एक ट्री होता है, जिसे सबट्री कहा जाता है।
• लीफ नोड्स. जिन वर्टिसेज़ की ठीक एक एज होती है, उन्हें पत्तियाँ या लीफ नोड्स कहते हैं। ये ट्री के एंडपॉइंट्स होते हैं।

ट्री ग्राफ़ अन्य ग्राफ़ों से कैसे भिन्न होते हैं? 

सामान्य ग्राफ़ों के विपरीत, ट्री में साइकिल्स नहीं होतीं। इसका अर्थ है कोई भी ऐसा ग्राफ़ जिसमें साइकिल हो, उसे ट्री के रूप में वर्गीकृत नहीं किया जा सकता। 

$$n$$ वर्टिसेज़ वाले ट्री में ठीक $$n−1$$ एजेज़ होते हैं, जबकि सामान्य ग्राफ़ों में एजों की संख्या परिवर्तनीय हो सकती है, जिनमें मल्टिपल एज और स्व-लूप्स भी शामिल हो सकते हैं। एक अन्य भिन्नता यह है कि ट्री हमेशा कनेक्टेड होते हैं, जबकि सामान्य ग्राफ़ डिसकनेक्टेड भी हो सकते हैं, जिनमें कई कॉम्पोनेंट्स होते हैं, जिनमें से प्रत्येक एक ट्री हो सकता है। 

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

अनुप्रयोग

ट्री कंप्यूटिंग और डेटा संगठन के सैद्धांतिक और व्यावहारिक दोनों पहलुओं में बुनियादी हैं। वे कई संरचनात्मक और एल्गोरिथ्मिक समस्याओं के लिए अत्यंत कुशल समाधान प्रदान करते हैं। उदाहरण के लिए: 

डेटा संरचनाएँ

• बाइनरी ट्रीज़: डेटा को पदानुक्रमित रूप से संगठित करने के लिए कंप्यूटर विज्ञान में उपयोग किए जाते हैं। उदाहरण में बाइनरी सर्च ट्री शामिल हैं, जो तेज़ डेटा प्राप्ति और सॉर्टिंग को सक्षम बनाते हैं।
• हीप्स: प्रायोरिटी क्यूज़ में अधिकतम या न्यूनतम तत्त्व को दक्षता से प्रबंधित और पुनः प्राप्त करने के लिए उपयोग होने वाला बाइनरी ट्री का प्रकार।
• B-ट्रीज़: डेटाबेस और फ़ाइल प्रणालियों में कुशल डेटा प्राप्ति और भंडारण के लिए उपयोग होते हैं, जो इन्सर्शन, डिलीशन और सर्च जैसे ऑपरेशनों का समर्थन करते हैं।

नेटवर्क डिज़ाइन

• रूटिंग: नेटवर्क रूटिंग प्रोटोकॉल्स (जैसे स्पैनिंग ट्रीज़) में ट्री का उपयोग नेटवर्क में डेटा ट्रांसमिशन के लिए सबसे कुशल पथ निर्धारित करने हेतु किया जाता है।
• ब्रॉडकास्टिंग: नेटवर्क डिज़ाइन में, ट्री संरचनाएँ कुशल डेटा प्रसारण में सहायक होती हैं, जिससे न्यूनतम पुनरावृत्ति के साथ सभी नोड्स तक डेटा पहुँचता है।

पदानुक्रम अभिविन्यास

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

पार्सिंग और सिंटैक्स विश्लेषण

• एब्स्ट्रैक्ट सिंटैक्स ट्रीज़ (ASTs): कम्पाइलर्स और इंटरप्रिटर्स में सोर्स कोड की वाक्यरचनात्मक संरचना का प्रतिनिधित्व करने के लिए उपयोग होते हैं। ASTs सिंटैक्स जाँच और कोड ऑप्टिमाइज़ेशन को सुगम बनाते हैं।

ग्राफ़ सिद्धांत के अनुप्रयोग

ग्राफ़ सिद्धांत के विभिन्न क्षेत्रों में व्यापक अनुप्रयोग हैं। यह जटिल समस्याओं को हल करने और प्रणालियों का अनुकूलन करने में महत्वपूर्ण भूमिका निभाता है। इसके उदाहरण निम्नलिखित अनुप्रयोगों में देखे जा सकते हैं: 

कंप्यूटर विज्ञान: नेटवर्किंग, एल्गोरिदम और डेटा संरचनाएँ

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

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

जीव विज्ञान: जैविक नेटवर्क का मॉडलिंग

ग्राफ़ सिद्धांत जीव विज्ञान में भी महत्त्वपूर्ण है। इसका उपयोग जटिल जैविक नेटवर्क के मॉडलिंग और विश्लेषण के लिए किया जाता है, जैसे: 

• प्रोटीन-प्रोटीन अंतःक्रिया नेटवर्क
• मेटाबोलिक पाथवे
• जीन विनियामक नेटवर्क

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

यह दृष्टिकोण शोधकर्ताओं को जैविक प्रणालियों के भीतर जटिल संबंधों को समझने, कार्यात्मक परिणामों की भविष्यवाणी करने और दवा विकास के संभावित लक्ष्यों की पहचान करने में मदद करता है।

समाज विज्ञान: सोशल नेटवर्क विश्लेषण

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

यह विश्लेषण सामाजिक संरचनाओं, प्रभाव के पैटर्न और समुदाय की गतिशीलता को समझने में मदद करता है। सेंट्रलिटी और कनेक्टिविटी जैसी अवधारणाओं को लागू करने से शोधकर्ताओं को प्रमुख प्रभावकों की पहचान करने, जानकारी के प्रसार का अध्ययन करने और सामाजिक व्यवहारों का विश्लेषण करने में मदद मिलती है।

परिवहन: ट्रैफ़िक प्रवाह और शहरी नियोजन 

अधिकांश लोग यह नहीं जानते, लेकिन सड़कों, चौराहों और ट्रांज़िट मार्गों का मॉडल ग्राफ़ के रूप में बनाया जाता है ताकि: 

• ट्रैफ़िक प्रवाह का अनुकूलन किया जा सके
• जाम कम किया जा सके
• मार्ग नियोजन में सुधार किया जा सके। 

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

सिंपल ग्राफ़ के निर्माण और विश्लेषण की चरण-दर-चरण रूपरेखा

आपने मूल बातें समझ ली हैं, और आप ग्राफ़ सिद्धांत के अनुप्रयोगों को समझते हैं। 

अब, आप अपना स्वयं का एक सिंपल ग्राफ़ बनाने और उसका विश्लेषण करने के लिए तैयार हैं। सरलता के लिए, हमने इस चरण-दर-चरण रूपरेखा को दो भागों में बाँटा है: 

• निर्माण 
• विश्लेषण

यहाँ से शुरू करने के लिए सबसे तार्किक भाग निर्माण है – आइए शुरू करें… 

सिंपल ग्राफ़ का निर्माण

चरण 1: समस्या को परिभाषित करें। 

मान लें कि हम सोशल नेटवर्क में मित्रों के एक छोटे नेटवर्क का मॉडल बनाना चाहते हैं। 

हम Python में NetworkX लाइब्रेरी का उपयोग कर सकते हैं, जो नेटवर्क विश्लेषण के लिए बनी है, इसे मॉडल करने हेतु। 

आइए एक ग्राफ़ बनाकर शुरू करें: 

# Import libraries 
import networkx as nx # Network analysis
import matplotlib.pyplot as plt # Data visualization
import pydot # Python interface to Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Create a graph
graph = nx.Graph() 
संचालित द्वारा

चरण 2: वर्टिसेज़ की पहचान करें। 

हमारे काल्पनिक सोशल नेटवर्क में चार व्यक्ति हैं: Alice, Bob, Carol और Dave। ये व्यक्ति हमारे ग्राफ़ में वर्टिसेज़ के रूप में दर्शाए जाएँगे – याद रखें, यह मॉडल की जा रही संरचना में किसी इकाई या स्थान का प्रतिनिधित्व करता है।

Python में वर्टिसेज़ इस प्रकार बनाएँगे:

# Add the nodes 
# graph.add_node("Alice") --> Add one node per time
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Add multiple nodesसंचालित द्वारा

चरण 3: एज तय करें। 

मान लें कि मित्रता संबंध इस प्रकार हैं:

• Alice, Bob और Carol की मित्र है।
• Bob, Alice और Dave का मित्र है।
• Carol, Alice की मित्र है।
• Dave, Bob का मित्र है।

इसका अर्थ है कि ये संबंध निम्न एजेज़ बनाते हैं:

• Alice-Bob
• Alice-Carol
• Bob-Dave

Python में एजेज़ इस प्रकार परिभाषित करेंगे: 

# Add the edges
# graph.add_edge("Alice", "Bob") --> Add one edge per time
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Ensuring all described edges are included
                     ]) # Add multiple edgesसंचालित द्वारा

चरण 4: ग्राफ़ ड्रॉ करें।

एक बार वर्टिसेज़ और एजेज़ परिभाषित हो जाने पर, हम संबंधों को देखने के लिए ग्राफ़ बना सकते हैं। नीचे दिया गया कोड स्निपेट लेबल लगे वर्टिसेज़ और एजेज़ के साथ नेटवर्क का ग्राफ़िकल प्रतिनिधित्व बनाएगा:

# Visualize the plot
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()संचालित द्वारा

आउटपुट: यह Alice, Bob, Carol और Dave के बीच बताए गए कनेक्शनों को दर्शाने वाला ग्राफ़ उत्पन्न करेगा।

यह कोड निम्न ग्राफ़ आउटपुट करता है: 

सोशल नेटवर्क का मॉडलिंग करता एक सिंपल ग्राफ़ [लेखक द्वारा निर्मित]

यदि आप अपना स्वयं का सोशल नेटवर्क मॉडल करना चाहते हैं, तो इस DataLab Notebook की प्रति बनाएँ और तदनुसार बदलाव करें। 

सिंपल ग्राफ़ का विश्लेषण

चरण 1: कनेक्टिविटी जाँचें। 

चूँकि हम किसी भी वर्टेक्स से किसी अन्य वर्टेक्स तक एजों के किसी अनुक्रम के माध्यम से जा सकते हैं, इसलिए ग्राफ़ कनेक्टेड है। 

इसे बेहतर ढंग से समझने के लिए, प्रत्येक वर्टेक्स-युग्म के बीच पाथ इस प्रकार है: 

• Alice से Bob: प्रत्यक्ष एज।
• Alice से Carol: प्रत्यक्ष एज।
• Alice से Dave: Bob के माध्यम से।
• Bob से Carol: Alice के माध्यम से।
• Bob से Dave: प्रत्यक्ष एज।
• Carol से Dave: Alice और Bob के माध्यम से।

चरण 2: प्रत्येक वर्टेक्स की डिग्री निर्धारित करें। 

याद रखें, हमने वर्टेक्स की डिग्री को “उससे जुड़े एजेज़ की संख्या” के रूप में परिभाषित किया था। इस ज्ञान को अपने उदाहरण पर लागू करते हुए, हमें मिलेगा: 

• Alice = डिग्री 2 (Bob और Carol से जुड़ी)
• Bob = डिग्री 2 (Alice और Dave से जुड़ा)
• Carol = डिग्री 1 (Alice से जुड़ी)
• Dave = डिग्री 1 (Bob से जुड़ा)

प्रत्येक डिग्री का निर्धारण, दी गई मित्रताओं के आधार पर, प्रत्येक वर्टेक्स से संबंधित एजेज़ की संख्या गिनकर किया जाता है।

चरण 3: पाथ और साइकिल्स की पहचान करें।

Alice और Dave के बीच एक पाथ Alice → Bob → Dave हो सकता है।

ग्राफ़ में कोई साइकिल नहीं है, क्योंकि ऐसा कोई पाथ नहीं जो प्रारंभिक वर्टेक्स पर लौटे बिना कदमों को दोहराए।

चरण 4: सेंट्रलिटी ज्ञात करें।

Alice और Bob इस नेटवर्क में केंद्रीय हैं, क्योंकि वे प्रत्येक तीन अन्य वर्टिसेज़ से जुड़ते हैं। Carol और Dave कम केंद्रीय हैं, प्रत्येक केवल एक अन्य वर्टेक्स से जुड़ते हैं।

निष्कर्ष

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

जब आप ग्राफ़ सिद्धांत का और अन्वेषण करें, तो याद रखें कि इसके सिद्धांत मात्र सैद्धांतिक नहीं हैं—वे वास्तविक दुनिया की चुनौतियों का सामना करने, कनेक्टिविटी में सुधार करने और सिस्टम दक्षता बढ़ाने के लिए आवश्यक हैं। ग्राफ़ सिद्धांत की ठोस समझ आपकी समस्या-समाधान क्षमता को बढ़ाएगी और हमारे आसपास की आपस में जुड़ी प्रणालियों पर गहरी दृष्टि प्रदान करेगी।

ग्राफ़ सिद्धांत की अपनी समझ विकसित करने के लिए, इन उन्नत संसाधनों को देखें जो हमने इस लेख में कवर की गई बातों को आगे बढ़ाते हैं: 

• ग्राफ़ न्यूरल नेटवर्क्स (GNNs) का एक व्यापक परिचय 
• Python में NetworkX के साथ ग्राफ़ ऑप्टिमाइज़ेशन
• Python ट्यूटोरियल में डिसीजन ट्री क्लासिफ़िकेशन