कनेक्टिविटी, दूरी और फैले हुए पेड़

फैला हुआ पेड़

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

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

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

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

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

कनेक्टिविटी

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

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

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

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

वर्टेक्स कनेक्टिविटी। किसी ग्राफ़ की शीर्ष संयोजकता कम से कम नोड्स की संख्या है जिसका विलोपन इसे डिस्कनेक्ट करता है।

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

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

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

दूरी

दो नोड्स के बीच की दूरी की गणना सबसे कम सामान्य पूर्वज के रूप में की जा सकती है। निम्नलिखित सूत्र है।

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca)
'd1' and 'd2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of d1 and d2
Dist(d1, d2) is the distance between d1 and d2.