This post is also available in: English العربية (Arabic)
नेटवर्क क्या होता है?
कंप्यूटर शब्दावली में, एक नेटवर्क में दो या अधिक कंप्यूटर होते हैं जो संसाधनों को साझा करने के लिए जुड़े होते हैं (जैसे प्रिंटर और सीडी), फाइलों का आदान-प्रदान, या इलेक्ट्रॉनिक संचार की अनुमति देते हैं। किसी नेटवर्क के कंप्यूटरों को केबल, टेलीफोन लाइनों, रेडियो तरंगों, उपग्रहों या अवरक्त प्रकाश किरणों (इंफ़्रा रेड लाइट) के माध्यम से जोड़ा जा सकता है। न केवल कंप्यूटर, यहां तक कि अन्य संचार उपकरण जैसे सेल फोन नेटवर्क के माध्यम से जुड़ने के कारण कार्य करते हैं। एक नेटवर्क कनेक्टेड ऑब्जेक्ट का एक संग्रह होता है। हम वस्तुओं को नोड्स के रूप में उल्लेख करते हैं और आमतौर पर उन्हें बिंदु के रूप में दर्शाते हैं। हम नोड्स के बीच के कनेक्शन का उल्लेख एज (edge) से करते हैं और उसे बिंदुओं के बीच की रेखाओं के रूप में दर्शाते हैं।
ग्राफ़ क्या होता है?
इकाइयों के एक समूह के बीच परस्पर संबंध दिखाने के लिए नेटवर्क आरेख को ग्राफ़ के रूप में भी जाना जाता है। प्रत्येक इकाई को एक नोड (या शीर्ष) द्वारा दर्शाया जाता है। नोड्स के बीच का संबंध लिंक (या एजजेज़) के माध्यम से दर्शाया गया है।
ग्राफ एक प्रकार की डेटा स्ट्रक्चर हैं जिनका उपयोग वस्तुओं और संस्थाओं के बीच युग्मक संबंधों का अध्ययन करने के लिए किया जाता है। यह असतत गणित की एक शाखा है और कंप्यूटर विज्ञान, रसायन विज्ञान, भाषा विज्ञान, संचालन अनुसंधान (ऑपरेशन्स रिसर्च), समाजशास्त्र, आदि में कई अनुप्रयोगों में इसका उपयोग होता है। औपचारिक रूप से एक ग्राफ़ G = (V, E) में शीर्षों (vertices) V = {V1, V2, V3, …} और एजजेज़ का सेट E = {E1, E2, E3, …} होता है। अलग-अलग कोने के अनियंत्रित जोड़े का सेट, जिनके तत्वों को ग्राफ G के एजजेज़ कहा जाता है जैसे कि प्रत्येक किनारे को कोने के एक अनियोजित जोड़ी (Vi, Vj) से पहचाना जाता है।
ग्राफ से जुड़ी शब्दावली
- uऔर vको एज्ज (u, v) के एन्ड वर्टिसिस कहा जाता है।
- यदि दो एजजेज़ पर समान छोर होते हैं तो उन्हें समानांतर एजजेज़ कहा जाता है।
- एज्ज (u, v) को लूप कहा जाता है।
- एक ग्राफ को सिंपल ग्राफ तब कहा जाता है अगर इसमें कोई समानांतर एजजेज़ और लूप नहीं होता है।
- यदि ग्राफ में कोई भी एज्ज नहीं है तो उसे एम्प्टीग्राफ कहा जाता है।
- एक ग्राफ अशक्त ग्राफ होता है यदि इसमें कोई शीर्ष नहीं हैं।
- केवल 1 शीर्ष ग्राफ को ट्रिविअल ग्राफ कहते हैं।
- Edges are adjacent if they have a common vertex.
- वर्टिसिस अडजैसेन्ट होते हैं यदि उनमें कॉमन एज्ज होता है।
- वर्टेक्स v की डिग्री, d(v) के रूप में लिखी जाती है, जो v के साथ एजजेज़ की संख्या होती है। हम लूप को दो बार गिनते हैं और समानांतर किनारे अलग से गिने जाते हैं।
ग्राफ के ऍप्लिकेशन्स
- कंप्यूटर विज्ञान: कंप्यूटर विज्ञान में, ग्राफ का उपयोग संचार, डेटा संगठन, कम्प्यूटेशनल उपकरणों, आदि के नेटवर्क का प्रतिनिधित्व करने के लिए किया जाता है।
- भौतिकी और रसायन विज्ञान: रसायन विज्ञान और भौतिकी में अणुओं का अध्ययन करने के लिए ग्राफ सिद्धांत का भी उपयोग किया जाता है।
- सामाजिक विज्ञान: समाजशास्त्र में ग्राफ सिद्धांत का भी व्यापक रूप से उपयोग किया जाता है।
- गणित: इसमें, रेखागणित ज्यामिति और टोपोलॉजी के कुछ हिस्सों जैसे knot theory में उपयोगी होते हैं।
- जीव विज्ञान: जीव विज्ञान और संरक्षण प्रयासों में ग्राफ सिद्धांत उपयोगी है।
बच्चों को समझाए गए ग्राफ प्रकार – ग्राफ के प्रकार
ग्राफ विभिन्न प्रकार के होते हैं और इन्हें मुख्य रूप से वर्गीकृत किया जा सकता है:
Null Graph
नल ग्राफ़ एक ऐसा ग्राफ़ होता है जिसमें इसके शीर्षों के बीच कोई एज्ज नहीं होता है। नल ग्राफ़ को एम्प्टी ग्राफ़ भी कहा जाता है।
उपरोक्त ग्राफ में, चार शीर्ष हैं लेकिन एक भी एज्ज नहीं है। यह नल ग्राफ का एक उदाहरण है।
Trivial Graph
ट्रिविअल ग्राफ एक ऐसा ग्राफ होता है जिसमें केवल एक शीर्ष होता है।
उपर्युक्त ग्राफ में, 1 द्वारा निरूपित केवल एक शीर्ष है।
Simple Graph
एक सिंपल ग्राफ एक अनडायरेक्टेड ग्राफ है जिसमें कोई समानांतर एजजेज़ और कोई लूप नहीं होते। एक सिंपल ग्राफ में जिसमें n वर्टिसिस हैं, हर वर्टेक्स की डिग्री अधिकतम (n – 1) होती है। उपरोक्त उदाहरण में, पहला ग्राफ़ सिंपल ग्राफ़ नहीं है क्योंकि इसमें A और B के बीच दो एजजेज़ हैं और इसमें एक लूप भी है। दूसरा ग्राफ एक सिंपल ग्राफ है क्योंकि इसमें कोई लूप और समानांतर एजजेज़ नहीं हैं।
Undirected Graph
अनडायरेक्टेड ग्राफ़ एक ऐसा ग्राफ़ है जिसके एजजेज़ को निर्देशित नहीं किया जाता है।
डायरेक्टेड ग्राफ़
डायरेक्टेड ग्राफ एक ग्राफ है जिसमें एजजेज़ को एरो द्वारा निर्देशित किया जाता है। डायरेक्टेड ग्राफ्स को डाईग्राफ्स भी कहा जाता है।
उपरोक्त ग्राफ में, प्रत्येक एज्ज को एक एरो द्वारा निर्देशित किया गया है। एक निर्देशित किनारे में A से B तक एक एरो है, जिसका अर्थ A, B से संबंधित है, लेकिन B, A से संबंधित नहीं है (नेटवर्क के संदर्भ में, A से B तक का मार्ग है, लेकिन B से A तक का कोई मार्ग नहीं है ।
Complete Graph
एक ग्राफ जिसमें प्रत्येक शीर्ष के जोड़े को जोड़ दिया जाता है, उसे कम्पलीट ग्राफ कहा जाता है। इसमें सभी संभव एजजेज़ शामिल होते हैं। उपरोक्त उदाहरण में, चूंकि ग्राफ़ में प्रत्येक शीर्ष एक एज्ज के माध्यम से सभी शेष शीर्ष से जुड़ा हुआ है, इसलिए, दोनों ग्राफ़ कम्पलीट ग्राफ़ हैं।
कनेक्टेड ग्राफ़
कनेक्टेड ग्राफ एक ग्राफ है जिसमें हम किसी भी अन्य शीर्ष से किसी भी शीर्ष पर जा सकते हैं। एक कनेक्टेड ग्राफ में, कम से कम एक एज्ज या पथ हर जोड़ी के बीच मौजूद है।
Disconnected Graph
डिस्कनेक्टेड ग्राफ वह ग्राफ होता है जिसमें किसी भी मार्ग का प्रत्येक जोड़े के बीच कोई पथ नहीं होता है।
उपर्युक्त ग्राफ में 3 और 0, 3 और 1, 3 और 2 के बीच और 4 और 0, 4 और 1 और 4 और 2 के बीच भी कोई पथ नहीं है।
रेगुलर ग्राफ़
रेगुलर ग्राफ एक ग्राफ होता है जिसमें सभी शीर्षों की डिग्री समान होती है। यदि सभी कोने की डिग्री k है, तो इसे k-रेगुलर ग्राफ कहा जाता है।
उपरोक्त ग्राफ में, प्रत्येक शीर्ष की डिग्री 3 है। इसलिए, यह एक 3-रेगुलर ग्राफ है।
Cyclic Graph
n शीर्षों के साथ एक ग्राफ (जहां n > = 3) और n किनारों के साथ n का एक चक्र बना है जिसके सभी किनारों को एक साइक्लिक ग्राफ के रूप में जाना जाता है। और एक ग्राफ जिसमें कम से कम एक चक्र होता है, उसे साइक्लिक ग्राफ कहा जाता है।
उपरोक्त ग्राफ में, B, C, E और D एक चक्र बनाते हैं, इसलिए, यह एक साइक्लिक ग्राफ है।
Acyclic Graph
एक ग्राफ जिसमें एक चक्र भी नहीं होता है, उसे असाइक्लिक ग्राफ कहा जाता है।
बाईपाटाइट ग्राफ़
बाईपाटाइट ग्राफ एक ग्राफ होता है जिसमें शीर्ष सेट को दो सेटों में विभाजित किया जा सकता है जो कि किनारे केवल सेट के बीच जाते हैं, उनके भीतर नहीं। एक ग्राफ G(V, E) को एक बाईपाटाइट ग्राफ कहा जाता है यदि इसके शीर्ष सेट V(G) को दो गैर-खाली डिस्चार्ज उप-समूह V1(G) और V2(G) में इस तरह से विघटित किया जा सकता है कि प्रत्येक किनारे इसका एक है V1(G) में अंतिम संयुक्त और V2(G) में दूसरा अंतिम बिंदु।
स्टार ग्राफ़
एक स्टार ग्राफ एक ग्राफ है जो बिल्कुल एक स्टार की तरह दिखता है जहां (n – 1) एजजेज़ एक एकल केंद्रीय शीर्ष से जुड़े होते हैं। n एजजेज़ के साथ एक स्टार ग्राफ Sn द्वारा दर्शाया जाता है।
All the above graphs are star graphs, as one vertex is connected to all the remaining vertices.
Weighted Graph
वेटेड ग्राफ एक ऐसा ग्राफ है जिसके किनारों को कुछ भार या संख्याओं के साथ लेबल किया गया है। वेटेड ग्राफ में पथ की लंबाई पथ में सभी एजजेज़ के भार का योग होता है।
उपरोक्त ग्राफ एक वेटेड ग्राफ है क्योंकि प्रत्येक एज्ज को वजन नामक मान के साथ लेबल किया गया है। दूरियों के साथ शहरों को दिखाने वाला एक ग्राफ वेटेड ग्राफ का एक और उदाहरण है।
Planar Graph
प्लेनर ग्राफ एक ग्राफ है जिसे हम एक प्लेन में इस तरह से खींच सकते हैं कि इसके दो किनारों को एक दूसरे को पार नहीं किया जाता है सिवाय एक शिखर पर जहां से वे आरम्भ होते हैं।
उपर्युक्त सभी ग्राफ प्लानेर ग्राफ हैं क्योंकि सभी ग्राफ़ की एजजेज़ एक-दूसरे को पार नहीं कर रही हैं।
नॉन-प्लैनर ग्राफ़
एक ऐसा ग्राफ जिसे बिना किसी एज्ज को पार किए बिना खींचा नहीं जा सकता है, गैर-प्लानर ग्राफ के रूप में जाना जाता है। दूसरे शब्दों में, एक ग्राफ जो कि एक प्लैनर ग्राफ नहीं है, नॉन-प्लैनर ग्राफ कहलाता है।
