स्पैनिंग ट्री
एक सरल परिभाषा यह है कि एक ट्री एक कनेक्टेड ग्राफ है जिसमें कोई साइकिल नहीं होती, जहां एक साइकिल हमें किसी नोड से स्वयं तक बिना किसी एज को दोहराए जाने देती है।
एक कनेक्टेड ग्राफ 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 के बीच की दूरी है।