Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

कनेक्टिविटी, दूरी, और स्पैनिंग ट्री


स्पैनिंग ट्री

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

एक कनेक्टेड ग्राफ G के लिए एक स्पैनिंग ट्री को G के सभी वर्टेक्स को समाहित करने वाले ट्री के रूप में परिभाषित किया जाता है।

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

ग्राफ में स्पैनिंग ट्री की कुल संख्या। यदि एक ग्राफ n वर्टेक्स के साथ एक पूर्ण ग्राफ है, तो स्पैनिंग ट्री की कुल संख्या n(n-2) है।

जहां n ग्राफ में नोड्स की संख्या को दर्शाता है। पूर्ण ग्राफ में, कार्य n नोड्स के साथ अलग-अलग लेबल वाले ट्रीज को गिनने के बराबर है जिसके लिए केली का सूत्र है।

कनेक्टिविटी

गणित और कंप्यूटर विज्ञान में, कनेक्टिविटी ग्राफ थ्योरी की बुनियादी अवधारणाओं में से एक है।

इसके लिए उन एलिमेंट्स (नोड्स या एज) की न्यूनतम संख्या की आवश्यकता होती है जिन्हें शेष नोड्स को आइसोलेटेड सबग्राफ में अलग करने के लिए हटाने की आवश्यकता होती है।

यह नेटवर्क फ्लो समस्याओं के सिद्धांत से निकटता से संबंधित है।

कनेक्टिविटी, दूरी, और स्पैनिंग ट्री

जब डैश्ड एज को हटा दिया जाता है तो यह ग्राफ डिस्कनेक्ट हो जाता है।

वर्टेक्स कनेक्टिविटी। एक ग्राफ की वर्टेक्स कनेक्टिविटी कम से कम उन नोड्स की संख्या है जिनके डिलीट होने से यह डिस्कनेक्ट हो जाता है।

वर्टेक्स कनेक्टिविटी को कभी-कभी "पॉइंट कनेक्टिविटी" या केवल "कनेक्टिविटी" कहा जाता है।

एज कनेक्टिविटी। एक ग्राफ से कम से कम उन एज की संख्या जिनके डिलीट होने से यह डिस्कनेक्ट हो जाता है, जिसे लाइन कनेक्टिविटी भी कहा जाता है।

एक डिस्कनेक्टेड ग्राफ की एज कनेक्टिविटी 0 होती है, जबकि एक कनेक्टेड ग्राफ की जिसमें ग्राफ ब्रिज है, 1 होती है।

दूरी

दो नोड्स के बीच की दूरी को लोएस्ट कॉमन एन्सेस्टर के संदर्भ में गणना की जा सकती है। निम्न सूत्र है।

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca) 'd1' और 'd2' दो दी गई कीज़ हैं 'root' दिए गए बाइनरी ट्री का रूट है। 'lca' d1 और d2 का लोएस्ट कॉमन एन्सेस्टर है Dist(d1, d2) d1 और d2 के बीच की दूरी है।
  1. डेटा स्ट्रक्चर में बाइनरी ट्री और गुण डेटा स्ट्रक्चर में बाइनरी ट्री और गुण

    इस खंड में हम बाइनरी ट्री डेटा स्ट्रक्चर के कुछ महत्वपूर्ण गुण देखेंगे। मान लीजिए हमारे पास ऐसा बाइनरी ट्री है।कुछ गुण हैं:लेवल l पर नोड्स की अधिकतम संख्या $2^{l-1}$ होगी। यहां लेवल रूट से नोड तक के पथ पर नोड्स की संख्या है, जिसमें रूट स्वयं शामिल है। हम रूट का लेवल 1 मान रहे हैं।ऊंचाई h के बाइनरी ट

  1. आईपी एड्रेस कैसे प्रबंधित करें और नेटवर्क कनेक्टिविटी का समस्या निवारण कैसे करें आईपी एड्रेस कैसे प्रबंधित करें और नेटवर्क कनेक्टिविटी का समस्या निवारण कैसे करें

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

  1. विंडोज 7 और 10 पर वनड्राइव कनेक्टिविटी समस्याएं [फिक्स] विंडोज 7 और 10 पर वनड्राइव कनेक्टिविटी समस्याएं [फिक्स]

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