सूचना विज्ञान में आलेख: परिभाषा, प्रकार, अनुप्रयोग, उदाहरण कंप्यूटर विज्ञान में ग्राफ का सिद्धांत

सूचना विज्ञान के ग्राफ तत्वों के संयोजन में संबंधों को परिभाषित करने का एक तरीका है। ये ग्राफ सिद्धांत के अध्ययन की मुख्य वस्तुएं हैं

बुनियादी परिभाषाएं

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

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

नेटवर्क के मॉडल

कंप्यूटर विज्ञान के ग्राफ नेटवर्क संरचनाओं के गणितीय मॉडल के रूप में कार्य करते हैं। निम्नलिखित आंकड़ा इंटरनेट की संरचना को दर्शाता है, जिसे ARPANET कहा जाता है, दिसंबर 1 9 70 में, जब उसके पास केवल 13 अंक थे। नोड्स कंप्यूटिंग केंद्र हैं, और किनारों उनके बीच एक सीधा संबंध के साथ दो कोने से जुड़ते हैं। यदि आप संयुक्त राज्य अमेरिका के सुपरिमाइज्ड मानचित्र पर ध्यान नहीं देते हैं, तो शेष छवि 13-नोड ग्राफ है जो पिछले वाले के समान है। इस मामले में, ऊर्ध्वाधर की वास्तविक व्यवस्था नगण्य है। यह महत्वपूर्ण है कि नोड्स एक दूसरे से जुड़े हुए हैं

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

मार्गों

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

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

चक्र

कंप्यूटर साइंस में विशेष रूप से महत्वपूर्ण प्रकार के ग्राफ चक्र हैं, जो एक अंगूठी संरचना का प्रतिनिधित्व करते हैं, जैसे कि नोड्स LINC, केस, CARN, HARV, बीबीएन, एमआईटी, लिनक्स के अनुक्रम। कम से कम तीन किनारों वाला मार्ग, जिसमें पहले और आखिरी नोड समान हैं, और अन्य अलग हैं, कंप्यूटर विज्ञान में चक्रीय ग्राफ हैं।

उदाहरण: चक्र एसआरआई, स्टैन, यूसीएलए, एसआरआई सबसे कम है, और एसआरआई, स्टैन, यूसीएलए, रैंड, बीबीएन, यूटीएए, एसआरआई बहुत बड़ा है।

वास्तव में, एआरपीएनईटी ग्राफ़ के प्रत्येक किनारे चक्र के अंतर्गत आते हैं यह जानबूझकर किया गया था: यदि उनमें से कोई भी विफल हो जाता है, तो एक नोड से दूसरे तक जाने की संभावना होगी। संचार और परिवहन व्यवस्था में चक्र अतिरेक प्रदान करने के लिए मौजूद हैं - वे एक अलग पथ पथ के साथ वैकल्पिक मार्ग प्रदान करते हैं। सामाजिक नेटवर्क में, चक्र भी अक्सर देखा जाता है। उदाहरण के लिए, जब आप पाते हैं कि आपकी पत्नी के चचेरे भाई का एक करीबी स्कूल दोस्त वास्तव में आपके भाई के साथ काम कर रहा है, तो यह एक चक्र है जिसमें आपकी, आपकी पत्नी, उसका चचेरा भाई, उसका स्कूल मित्र, उसका कर्मचारी (यानी आपका भाई) और, अंत में, फिर आप

जुड़ा हुआ ग्राफ: परिभाषा (सूचना विज्ञान)

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

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

घटकों

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

ग्राफ कनेक्टिविटी के घटकों में नोड्स का एक सबसेट है जिसमें:

• उपसमूह के प्रत्येक शीर्ष में किसी भी अन्य के लिए एक मार्ग है;
• एक सबसेट एक बड़े सेट का हिस्सा नहीं है जिसमें प्रत्येक नोड के पास किसी अन्य स्थान का मार्ग है।

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

अधिकतम घटक

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

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

दोस्तों का एक वैश्विक नेटवर्क

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

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

कुछ दुर्लभ मामलों में, जब दो अधिकतम घटकों को एक वास्तविक नेटवर्क में लंबे समय तक सह-अस्तित्व में रखा गया था, तो उनकी एकीकरण अप्रत्याशित, नाटकीय और आखिरकार, विनाशकारी परिणाम था।

घटक फ्यूजन क्रैश

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

अमेरिकन हाई स्कूल

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

दूरी और चौड़ाई की खोज

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

ऐसा करने के लिए, मार्ग की लंबाई निर्धारित करें, जो कि शुरू से लेकर अंत तक के चरणों की संख्या के बराबर है, यह है कि अनुक्रम में किनारों की संख्या जो इसे बनाती है उदाहरण के लिए, मार्ग एमआईटी, बीबीएन, रैंड, यूसीएलए की लंबाई 3 है, और एमआईटी, यूटीएएच 1 है। पथ की लंबाई का उपयोग करते हुए, यह एक बात कर सकता है कि दो नोड्स एक दूसरे के करीब या बहुत करीब के ग्राफ़ में स्थित हैं: दो कोने के बीच की दूरी को परिभाषित किया जाता है उनके बीच का सबसे छोटा रास्ता उदाहरण के लिए, LINC और एसआरआई के बीच की दूरी 3 है, हालांकि यह सुनिश्चित करने के लिए, आपको यह सुनिश्चित करना चाहिए कि उनके बीच 1 या 2 के बराबर कोई लम्बाई नहीं है।

खोज एल्गोरिदम व्यापक है

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

ऐसा करने का सबसे स्वाभाविक तरीका है और, इसलिए, सबसे प्रभावी, निम्न है (मित्रों के वैश्विक नेटवर्क के उदाहरण पर):

• सभी मित्रों को 1 की दूरी पर घोषित किया जाता है
• दोस्तों के सभी दोस्त (पहले से चिह्नित वाले लोगों की संख्या को नहीं मानते हैं) को 2 की दूरी पर स्थित घोषित किया जाता है
• उनके सभी दोस्त (फिर से, टैग किए गए लोगों की गिनती नहीं करते हैं) 3 की दूरी तक दूरस्थ घोषित किए जाते हैं।

इस तरह से आगे बढ़ते हुए, बाद की परतों में खोज की जाती है, जिनमें से प्रत्येक एक इकाई है जो पिछले एक से परे है प्रत्येक नई परत उन नोड्स से बना होती है, जो कि पिछली परतों में अभी तक शामिल नहीं हुई हैं, और जो पिछली परत के शीर्ष के साथ बढ़त दर्ज करते हैं।

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

चौड़ाई में खोज न केवल दोस्तों के नेटवर्क पर लागू किया जा सकता है, बल्कि किसी भी ग्राफ पर भी लागू किया जा सकता है।

दुनिया छोटा है

यदि आप मित्रों के वैश्विक नेटवर्क पर वापस जाते हैं, तो आप देख सकते हैं कि अधिकतम घटक के स्वामित्व को समझाते हुए तर्क, वास्तव में, कुछ और कहते हैं: न केवल पाठक उन दोस्तों के लिए मार्ग हैं जो उन्हें दुनिया की आबादी के बड़े हिस्से से जोड़ते हैं, लेकिन ये मार्ग आश्चर्यजनक रूप से कम हैं ।

इस विचार को "करीबी दुनिया की घटना" कहा जाता है: दुनिया छोटा लगता है, यदि आप सोचते हैं कि एक छोटा रास्ता क्या किसी भी दो लोगों से जोड़ता है

1 9 60 के दशक में स्टेनली मिल्ग्राम और उनके सहयोगियों द्वारा "छह हाथ मिलाने" के सिद्धांत का प्रयोग पहली बार किया गया था। सामाजिक नेटवर्किंग डेटा का कोई सेट नहीं है और 680 डॉलर के बजट के साथ, उसने लोकप्रिय विचार का परीक्षण करने का निर्णय लिया। इस समाप्ति के लिए, उन्होंने 296 बेतरतीब ढंग से चयनित आरंभकर्ताओं को बोस्टन के उपनगर में रहने वाले स्टॉक ब्रॉकर को एक पत्र भेजने के लिए कहा। आरंभकर्ताओं को इस उद्देश्य (पता और पेशा समेत) के बारे में कुछ व्यक्तिगत जानकारी दी गई थी और उन्हें इस पत्र को एक व्यक्ति को नाम से जानना था, उसी निर्देश के साथ कि जितनी जल्दी हो सके लक्ष्य तक पहुंच गया। प्रत्येक पत्र कई दोस्तों के हाथों से गुज़रे और एक चेन का गठन किया जो बोस्टन के बाहर एक एक्सचेंज ब्रोकर पर बंद हुआ।

लक्ष्य पर पहुंचने वाली 64 श्रृंखलाओं में, औसत लंबाई छह थी, जो दो दशक पहले जॉन गेयर द्वारा खेल के शीर्षक में की गई थी।

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