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

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

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

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

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

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

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

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

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

उनके स्पेक्ट्रम द्वारा निर्धारित रेखांकन

एक ग्राफ $G$ को उसके स्पेक्ट्रम द्वारा निर्धारित किया जाता है यदि $G$ के समान स्पेक्ट्रम वाला कोई अन्य ग्राफ $G$ के लिए समरूपी है।

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

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

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

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

कोस्पेक्ट्रल साथी की सबसे छोटी जोड़ी {K_1,4, C₄ ∪ K₁} है, जिसमें 5-शीर्ष् तारा और 4-वर्टेक्स चक्र काग्राफ संघ और सिंगल-शीर्ष् ग्राफ सम्मिलित है, जैसा कि कोलॉज और सिनोगोविट्ज़ द्वारा 1957 में बताया गया था ।

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

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

लगभग सभी पेड़ कॉस्पेक्ट्रल हैं, यानी, जैसे-जैसे शीर्षों की संख्या बढ़ती है, पेड़ों का वह अंश जिसके लिए एक कॉस्पेक्ट्रल ट्री निहित होता है, 1 हो जाता है।

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

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

सुनदा पद्धति के माध्यम से कोस्पेक्ट्रल ग्राफ भी बनाए जा सकते हैं।

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

चीजर असमानता

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

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

Main article: चीजर स्थिरांक (ग्राफ सिद्धांत)

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

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

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

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

चीजर असमानता

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

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

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

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

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

जहाँ $\lambda$ सामान्यीकृत लाप्लासियन का कम से कम गैर-तुच्छ अभिलक्षणिक मान है, और ${\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$ एक कम से कम अभिलक्षणिक मान वाले $\lambda _{\mathrm {min} }$के साथ $n$ कोने पर एक $k$-नियमित ग्राफ है। तब:

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

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

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

सामान्य ग्राफ के लिए जो आवश्यक रूप से नियमित नहीं हैं, स्वतंत्र संख्या के लिए एक समान ऊपरी सीमा $G$ के सामान्यीकृत लाप्लासियन के अधिकतम अभिलक्षणिक मान $\lambda '_{max}$ का उपयोग करके प्राप्त की जा सकती है:

$$\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 के मोनोग्राफ स्पेक्ट्रा ऑफ़ ग्राफ़्स में इस क्षेत्र में आज तक के लगभग सभी शोधों को संक्षेप में प्रस्तुत किया है। 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]