एक यादृच्छिक ग्राफ का व्यास महत्वपूर्ण क्यों है?
मैं एक ग्राफ के व्यास को देख सकता हूं , जिसे सबसे लंबे समय तक सबसे छोटे रास्ते के रूप में परिभाषित किया गया है, एक यादृच्छिक ग्राफ में एक गैर-तुच्छ मात्रा है जैसे यादृच्छिक ग्राफ$G(n,p)$ के बीच के किनारों को जोड़कर बनाया गया है $n$ स्वतंत्र रूप से संभावना के साथ अंक $p$।
लेकिन क्या यह गणितीय रूप से महत्वपूर्ण है? अन्य मौलिक ग्राफ विचारों से क्या संबंध है? इसके अलावा, अगर मैं ग्राफ़ पर कुछ बाधाएँ जोड़ता हूं, जैसे कि डिग्री वितरण, या कोने पर स्थानिक अवरोध (यानी यादृच्छिक ज्यामितीय ग्राफ़), तो यह ग्राफ व्यास के महत्व को क्या करता है?
जवाब
ग्राफ़ का व्यास अपने आप में महत्वपूर्ण है, उसी तरह से वर्णनात्मक संख्या या अधिकतम डिग्री है। यदि आप अपना ग्राफ किसी नेटवर्क को बनाना चाहते हैं, तो यह आपको अधिकतम संख्या में 'हॉप्स' बताता है, जिसे एक नोड से किसी अन्य पर प्राप्त करने के लिए लेना होता है। यदि आपका ग्राफ ज्यामितीय रूप से एम्बेडेड है, तो कहें, एक ग्राफ जहां प्रत्येक किनारे पर लंबाई 1 की एक सीधी रेखा है, तो (एब्सट्रेक्ट) ग्राफ का व्यास एम्बेडेड ग्राफ के व्यास पर एक ऊपरी बाउंड है, जिसे सबसेट माना जाता है$\mathbb{R}^n$।
लश्कर $D$ एक ग्राफ का व्यास हो, $n$ इसका आदेश, $\Delta$ इसकी अधिकतम डिग्री और $\kappa$इसकी कनेक्टिविटी। व्यास कैसे व्यवहार करते हैं, इसके लिए कुछ सामान्य अनुमान (ये प्रवृत्तियाँ हैं, सिद्धांत नहीं):
- यदि किसी ग्राफ़ में कम व्यास है, और कई कोने हैं, तो इसके कई किनारे होने चाहिए, और इन किनारों को कुछ हद तक 'समान' तरीके से वितरित किया जाना चाहिए, ताकि किसी भी दो कोने दूर न हों।
- यदि रेखांकन की संख्या की तुलना में ग्राफ का व्यास बहुत बड़ा है, तो ग्राफ़ में कम किनारों हैं।
- उपरोक्त बिंदुओं के समान नस में, व्यास और अधिकतम डिग्री एक साथ कुल संख्याओं को जोड़ते हैं जो एक ग्राफ हो सकता है। स्वाभाविक रूप से, यदि आप गहराई का वृक्ष बनाते हैं तो आप एक ग्राफ से अधिक कोने नहीं निकाल सकते$D$ वह शाखाएँ लगभग बाहर $\Delta-1$प्रत्येक परत पर समय, कुछ अतिरिक्त किनारों के साथ चीजों को बंद करने के लिए। इस बाउंड का अध्ययन डिग्री व्यास की समस्या का विषय है ।
- जबकि व्यास और अधिकतम डिग्री बाध्य है $n$ऊपर से, व्यास और कनेक्टिविटी ने इसे नीचे से बांधा है। बाउंड लगभग जैसा दिखता है$n \geq \kappa \cdot (D-1)$।
- व्यास ग्राफ के परिधि को भी संकुचित करता है। संक्षेप में, यदि व्यास कम है, और ग्राफ में कोई भी चक्र है, तो उसमें कम लंबाई का चक्र होना चाहिए।
अंत में, व्यास एक अच्छी जटिलता के रूप में काम करता है। यदि आप सामान्य रेखांकन में कुछ संरचना या विशेषता का अध्ययन करने की कोशिश कर रहे हैं और निराशाजनक रूप से खो रहे हैं, तो अक्सर यह विचार करना उपयोगी होता है कि व्यास 2 के रेखांकन में क्या होता है (विशेष रूप से इसके साथ जाने के लिए कुछ अन्य बाधा या प्रतिबंधित ग्राफ वर्ग दिया गया)। जो इसे काफी भाग्यशाली बनाता है कि लगभग सभी ग्राफ़ में व्यास 2 है!