विस्तारक ग्राफ

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

परिभाषाएँ

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

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

किनारे का विस्तार

किनारे का विस्तार भी आइसोपेरिमेट्रिक संख्या या चीजर स्थिरांक h(G) एक ग्राफ सिद्धांत का G पर n शिखर के रूप में परिभाषित किया गया है।

$h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},$

जहाँ $\partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\in V(G)\setminus S\},$

जिसे इस रूप में भी लिखा जा सकता है ∂S = E(S, S) साथ S := V(G) \ S का पूरक S और

$E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}$ शीर्षों के उपसमुच्चय के बीच के किनारे A,B ⊆ V(G).

समीकरण में, न्यूनतम सभी गैर-रिक्त सेटों पर होती है S अधिक से अधिक n⁄2 शिखर और ∂S की किनारा सीमा S है अर्थात, किनारों का सेट S में ठीक एक समापन बिंदु के साथ है।.

सहज रूप से,

$\min {|\partial S|}=\min E({S},{\overline {S}})$

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

ध्यान दें कि में min |∂S|, ऑप्टिमाइज़ेशन या तो अधिक समान रूप से किया जा सकता है 0 ≤ |S| ≤ n⁄2 या किसी गैर-रिक्त सबसेट पर, चूंकि $E(S,{\overline {S}})=E({\overline {S}},S)$. के लिए सही नहीं है h(G) द्वारा सामान्यीकरण के कारण |S|.यदि हम h(G) को सभी गैर-रिक्त सबसेट पर एक अनुकूलन के साथ लिखना चाहते हैं तो हम इसे फिर से लिख सकते हैं

$h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.$

वर्टेक्स विस्तार

वर्टेक्स आइसोपेरिमेट्रिक संख्या h_out(G) वर्टेक्स विस्तरण या ग्राफ G का आवर्धन इस रूप में परिभाषित किया गया है।

$h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},$

जहाँ ∂_out(S) की बाहरी सीमा S है अर्थात शीर्षों का सेट V(G) \ S कम से कम एक निकटतम के साथ S के रूप में होते है. इस परिभाषा के एक अनुसार जिसे अद्वितीय निकटतम विस्तार कहा जाता है ∂_out(S) को V में शीर्षों के सेट द्वारा S में ठीक एक निकटतम के साथ प्रतिस्थापित किया जाता है।.

शीर्ष आइसोपेरिमेट्रिक संख्या h_in(G) एक ग्राफ का G द्वारा परिभाषित किया जाता है।

$h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},$

जहाँ $\partial _{\text{in}}(S)$ की भीतरी सीमा S है, अर्थात शीर्षों का सेट S कम से कम एक निकटतम के साथ V(G) \ S के रूप में होता है.

वर्णक्रमीय विस्तार

जब G नियमित ग्राफ के रूप में होता है, तो विस्तार की एक रेखीय बीजगणितीय परिभाषा d के आसन्न आव्यूह A = A(G) का G, के अभिलक्षणिक मान ​​​​के आधार पर संभव होता है, जहाँ A_ij शीर्षों i और j के बीच किनारों की संख्या के रूप में होती है।. क्योंकि A सममित आव्यूह है, वर्णक्रमीय प्रमेय का तात्पर्य है A में n वास्तविक मूल्यवान अभिलक्षणिक मान λ₁ ≥ λ₂ ≥ … ≥ λ_n. के रूप में हैं यह ज्ञात है कि ये सभी अभिलक्षणिक मान ​​ [−d, d] में हैं और अधिक विशेष रूप से यह ज्ञात है कि λ_n = −d यदि और केवल यदि G द्विपक्षीय रूप में है।

अधिक औपचारिक रूप से, हम एक n वर्टेक्स d-नियमित ग्राफ़ को संदर्भित करते हैं

$$