स्पेक्ट्रल ग्राफ सिद्धांत

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

एक साधारण अप्रत्यक्ष ग्राफ का आसन्न मैट्रिक्स एक वास्तविक संख्या सममित मैट्रिक्स है और इसलिए ऑर्थोगोनल विकर्णीकरण है; इसके eigenvalues ​​वास्तविक बीजगणितीय पूर्णांक हैं।

जबकि आसन्न मैट्रिक्स वर्टेक्स लेबलिंग पर निर्भर करता है, मैट्रिक्स का इसका स्पेक्ट्रम एक ग्राफ अपरिवर्तनीय है, हालांकि पूर्ण नहीं है।

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

कोस्पेक्ट्रल रेखांकन

दो ग्राफ़ को कोस्पेक्ट्रल या आइसोस्पेक्ट्रल कहा जाता है यदि ग्राफ़ के आसन्न मैट्रिसेस आइसोस्पेक्ट्रल हैं, अर्थात, यदि आसन्न मैट्रिसेस में आइगेनवैल्यूज़ के समान multiset हैं।

दो कोस्पेक्ट्रल एननेहेड्रॉन, सबसे छोटा संभव कॉस्स्पेक्ट्रल बहुफलकीय ग्राफ

कोस्पेक्ट्रल ग्राफ को ग्राफ समरूपता नहीं होना चाहिए, लेकिन आइसोमोर्फिक ग्राफ हमेशा कॉस्पेक्ट्रल होते हैं।

=== उनके स्पेक्ट्रम === द्वारा निर्धारित रेखांकन एक ग्राफ $G$ कहा जाता है कि इसके स्पेक्ट्रम द्वारा निर्धारित किया जाता है यदि उसी स्पेक्ट्रम के साथ कोई अन्य ग्राफ $G$ के लिए आइसोमॉर्फिक है $G$.

उनके स्पेक्ट्रम द्वारा निर्धारित रेखांकन के परिवारों के कुछ पहले उदाहरणों में शामिल हैं:

• पूरा रेखांकन।
• परिमित तारे के समान वृक्ष।

कोस्पेक्ट्रल साथी

ग्राफ़ की एक जोड़ी को कोस्पेक्ट्रल साथी कहा जाता है यदि उनके पास एक ही स्पेक्ट्रम है, लेकिन गैर-आइसोमोर्फिक हैं।

कोस्पेक्ट्रल साथी की सबसे छोटी जोड़ी {के_1,4, सी₄ ∪ के₁}, जिसमें 5-वर्टेक्स तारा (ग्राफ सिद्धांत) और 4-वर्टेक्स चक्र (ग्राफ थ्योरी) का ग्राफ संघ और सिंगल-वर्टेक्स ग्राफ शामिल है, जैसा कि Collatz और Sinogowitz द्वारा रिपोर्ट किया गया है 1957 में।

पॉलीहेड्रल ग्राफ़ कॉस्पेक्ट्रल साथी की सबसे छोटी जोड़ी एनीहेड्रॉन है जिसमें आठ कोने हैं।

कोस्पेक्ट्रल ग्राफ ढूँढना

लगभग सभी पेड़ (ग्राफ थ्योरी) कॉस्पेक्ट्रल हैं, यानी, जैसे-जैसे वर्टिकल की संख्या बढ़ती है, पेड़ों का अंश जिसके लिए एक कॉस्पेक्ट्रल ट्री मौजूद होता है, 1 हो जाता है।

नियमित रेखांकन की एक जोड़ी कोस्पेक्ट्रल होती है यदि और केवल यदि उनके पूरक कोस्पेक्ट्रल हैं। दूरी-नियमित ग्राफ़ की एक जोड़ी कोस्पेक्ट्रल होती है यदि और केवल यदि उनके पास एक ही प्रतिच्छेदन सरणी हो।

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

चीजर असमानता

प्रसिद्ध चीगर स्थिरांक#चीगर.27s असमानता|रीमैनियन ज्यामिति से चीगर की असमानता में लाप्लासियन मैट्रिक्स से जुड़ा एक असतत एनालॉग है; यह शायद स्पेक्ट्रल ग्राफ सिद्धांत में सबसे महत्वपूर्ण प्रमेय है और एल्गोरिथम अनुप्रयोगों में सबसे उपयोगी तथ्यों में से एक है। यह लाप्लासियन के दूसरे eigenvalue के माध्यम से एक ग्राफ के सबसे कम कटौती का अनुमान लगाता है।

चीजर स्थिरांक

Main article: Cheeger constant (graph theory)

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

अधिक औपचारिक रूप से, n कोने पर एक ग्राफ G के चीजर स्थिरांक h(G) को इस रूप में परिभाषित किया गया है

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

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

चीजर असमानता

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

${\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.$

यह असमानता मार्कोव श्रृंखलाओं के लिए चीजर बाध्य से निकटता से संबंधित है और इसे चीगर कॉन्सटेंट#चीगर.27s असमानता|रीमैनियन ज्यामिति में चीगर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।

सामान्य रूप से जुड़े ग्राफ़ के लिए जो आवश्यक रूप से नियमित नहीं हैं, चुंग द्वारा एक वैकल्पिक असमानता दी गई है

${\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},$

कहाँ $\lambda$ सामान्यीकृत लाप्लासियन का कम से कम गैर-तुच्छ eigenvalue है, और ${\mathbf {h} }(G)$ (सामान्यीकृत) चीगर स्थिरांक है

${\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}$

कहाँ ${\mathrm {vol} }(Y)$ में शीर्षों की डिग्री का योग है $Y$.

हॉफमैन-डेल्सर्ट असमानता

मूल रूप से एलन जे हॉफमैन और फिलिप डेल्सर्ट के कारण नियमित ग्राफ में स्वतंत्र सेट (ग्राफ सिद्धांत) के लिए एक ईगेनवैल्यू बाध्य है। लगता है कि $G$ एक है $k$-नियमित ग्राफ पर $n$ कम से कम eigenvalue वाले कोने $\lambda _{\mathrm {min} }$. तब:

$$\alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}$$

कहाँ $\alpha (G)$ इसकी स्वतंत्रता संख्या को दर्शाता है।

इस सीमा को स्थापित करने के लिए लागू किया गया है उदा। एर्दोस-को-राडो प्रमेय के बीजगणितीय प्रमाण और परिमित क्षेत्रों पर उप-स्थानों के परिवारों को प्रतिच्छेद करने के लिए इसका एनालॉग। सामान्य रेखांकन के लिए जो आवश्यक रूप से नियमित नहीं हैं, स्वतंत्रता संख्या के लिए एक समान ऊपरी सीमा अधिकतम eigenvalue का उपयोग करके प्राप्त की जा सकती है $\lambda '_{max}$ सामान्यीकृत लाप्लासियन काका $G$:

$$\alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}$$

कहाँ ${\mathrm {maxdeg} }$ और ${\mathrm {mindeg} }$ में अधिकतम और न्यूनतम डिग्री को निरूपित करें $G$, क्रमश। यह अधिक सामान्य असमानता का परिणाम है (पृष्ठ 109 इंच ):

$${\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G))$$

कहाँ $X$ वर्टिकल और का एक स्वतंत्र सेट है ${\mathrm {vol} }(Y)$ में शीर्षों की डिग्री के योग को दर्शाता है $Y$ .

ऐतिहासिक रूपरेखा

स्पेक्ट्रल ग्राफ सिद्धांत 1950 और 1960 के दशक में उभरा। ग्राफ के संरचनात्मक और वर्णक्रमीय गुणों के बीच संबंध पर ग्राफ सिद्धांत अनुसंधान के अलावा, एक अन्य प्रमुख स्रोत क्वांटम रसायन विज्ञान में शोध था, लेकिन काम की इन दो पंक्तियों के बीच संबंध बहुत बाद तक खोजे नहीं गए थे। 1980 का मोनोग्राफ स्पेक्ट्रा ऑफ़ ग्राफ़ Cvetković द्वारा, Doob, और Sachs ने इस क्षेत्र में आज तक के लगभग सभी शोधों को संक्षेप में प्रस्तुत किया है। 1988 में इसे ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणामों के सर्वेक्षण द्वारा अद्यतन किया गया था। स्पेक्ट्रा ऑफ़ ग्राफ़्स (1995) के तीसरे संस्करण में इस विषय में हाल के योगदानों का सारांश शामिल है।2000 के दशक में तोशिवा यह रेत है द्वारा निर्मित और विकसित असतत ज्यामितीय विश्लेषण भारित ग्राफ़ से जुड़े असतत लाप्लासियन के संदर्भ में वर्णक्रमीय ग्राफ सिद्धांत से संबंधित है, और स्पेक्ट्रल आकार विश्लेषण सहित विभिन्न क्षेत्रों में आवेदन पाता है। हाल के वर्षों में, वर्णक्रमीय ग्राफ सिद्धांत का विस्तार कई वास्तविक जीवन के अनुप्रयोगों में अक्सर सामने आने वाले वर्टेक्स-अलग-अलग ग्राफ़ तक हो गया है।

यह भी देखें

• मजबूत नियमित ग्राफ
• बीजगणितीय कनेक्टिविटी
• बीजगणितीय ग्राफ सिद्धांत
• स्पेक्ट्रल क्लस्टरिंग
• वर्णक्रमीय आकार विश्लेषण
• इंडेक्स रोड
• लोवाज़ थीटा
• विस्तारक ग्राफ

संदर्भ

• Alon; Spencer (2011), The probabilistic method, Wiley.
• Brouwer, Andries; Haemers, Willem H. (2011), Spectra of Graphs (PDF), Springer
• Hoory; Linial; Wigderson (2006), Expander graphs and their applications (PDF)
• Chung, Fan (1997). American Mathematical Society (ed.). Spectral Graph Theory. Providence, R. I. ISBN 0821803158. MR 1421568[first 4 chapters are available in the website]{{cite book}}: CS1 maint: postscript (link)
• Schwenk, A. J. (1973). "Almost All Trees are Cospectral". In Harary, Frank (ed.). New Directions in the Theory of Graphs. New York: Academic Press. ISBN 012324255X. OCLC 890297242.

बाहरी संबंध

• Spielman, Daniel (2011). "Spectral Graph Theory" (PDF). [chapter from Combinatorial Scientific Computing]
• Spielman, Daniel (2007). "Spectral Graph Theory and its Applications". [presented at FOCS 2007 Conference]
• Spielman, Daniel (2004). "Spectral Graph Theory and its Applications". [course page and lecture notes]