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

Latest revision as of 17:42, 17 May 2023

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

चीजर असमानता

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

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

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

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

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

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

चीजर असमानता

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

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

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

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

{\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$ में शीर्षों के अंशो का योग है।

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

मूल रूप से एलन जे हॉफमैन और फिलिप डेल्सर्ट के कारण नियमित ग्राफ में स्वतंत्र समूह के लिए एक अभिलक्षणिक मान बाध्य है।^[13] मान लीजिए है कि $G$ एक कम से कम अभिलक्षणिक मान वाले $\lambda _{\mathrm {min} }$ के साथ $n$ कोने पर एक $k$ -नियमित ग्राफ है। तब:

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

जहाँ

\alpha (G)

इसकी स्वतंत्र संख्या को दर्शाता है।

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

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

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

जहाँ

{\mathrm {maxdeg} }

और

{\mathrm {mindeg} }

G

में क्रमशः अधिकतम और न्यूनतम डिग्री दर्शाते हैं। यह अधिक सामान्य असमानता का परिणाम है (पृष्ठ 109 में^[12]):

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

जहाँ

X

शीर्षों का एक स्वतंत्र समुच्चय है और

{\mathrm {vol} }(Y)

Y

में शीर्षों की डिग्री के योग को दर्शाता है।

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

स्पेक्ट्रल ग्राफ सिद्धांत 1950 और 1960 के दशक में उभरा था। ग्राफ के संरचनात्मक और वर्णक्रमीय गुणों के बीच संबंध पर ग्राफ सैद्धांतिक शोध के अलावा, एक अन्य प्रमुख स्रोत क्वांटम रसायन विज्ञान में शोध था, लेकिन काम की इन दो पंक्तियों के बीच संबंध बहुत बाद तक खोजे नहीं गए थे।^[15] सीवेटकोविच, डूब और साक्स द्वारा 1980 के मोनोग्राफ स्पेक्ट्रा ऑफ़ ग्राफ़्स^[16] में इस क्षेत्र में आज तक के लगभग सभी शोधों को संक्षेप में प्रस्तुत किया है। 1988 में इसे ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणामों के सर्वेक्षण द्वारा अद्यतन किया गया था।^[17] स्पेक्ट्रा ऑफ़ ग्राफ़्स (1995) के तीसरे संस्करण में इस विषय में हाल के योगदानों का सारांश सम्मिलित है।^[15]2000 के दशक में तोशिकाज़ू सुनदा द्वारा निर्मित और विकसित असतत ज्यामितीय विश्लेषण भारित ग्राफ़ से जुड़े असतत लाप्लासियन के संदर्भ में वर्णक्रमीय ग्राफ सिद्धांत से संबंधित है,^[18] और स्पेक्ट्रल आकार विश्लेषण सहित विभिन्न क्षेत्रों में आवेदन पाता है।हाल के वर्षों में, वर्णक्रमीय ग्राफ सिद्धांत का विस्तार वर्टेक्स-विभिन्न ग्राफों तक हो गया है, जो प्रायः कई वास्तविक जीवन अनुप्रयोगों में सामने आते हैं।^[19]^[20]^[21]^[22]

यह भी देखें

संदर्भ

↑ Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.
↑ Weisstein, Eric W. "Cospectral Graphs". MathWorld.
↑ Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices", Journal of Chemical Information and Modeling, 34 (2): 428–431, doi:10.1021/ci00018a033.
↑ Schwenk (1973), pp. 275–307.
↑ Godsil, Chris (November 7, 2007). "Are Almost All Graphs Cospectral?" (PDF).
↑ Sunada, Toshikazu (1985), "Riemannian coverings and isospectral manifolds", Ann. of Math., 121 (1): 169–186, doi:10.2307/1971195, JSTOR 1971195.
↑ Brouwer & Haemers 2011
↑ Definition 2.1 in Hoory, Linial & Wigderson (2006)
↑ J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.
↑ Alon & Spencer 2011.
↑ Theorem 2.4 in Hoory, Linial & Wigderson (2006)
↑ ^12.0 ^12.1 ^12.2 Chung, Fan (1997). American Mathematical Society (ed.). स्पेक्ट्रल ग्राफ थ्योरी. Providence, R. I. ISBN 0821803158. MR 1421568[first 4 chapters are available in the website]{{cite book}}: CS1 maint: postscript (link)
↑ Godsil, Chris (May 2009). "Erdős-Ko-Rado Theorems" (PDF).
↑ Godsil, C. D.; Meagher, Karen (2016). Erdős-Ko-Rado theorems : algebraic approaches. Cambridge, United Kingdom. ISBN 9781107128446. OCLC 935456305.{{cite book}}: CS1 maint: location missing publisher (link)
↑ ^15.0 ^15.1 Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1
↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)
↑ Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणाम. Annals of Discrete mathematics. ISBN 0-444-70361-6.
↑ Sunada, Toshikazu (2008), "Discrete geometric analysis", Proceedings of Symposia in Pure Mathematics, 77: 51–86, doi:10.1090/pspum/077/2459864, ISBN 9780821844717.
↑ Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre (March 2016). "रेखांकन पर शीर्ष-आवृत्ति विश्लेषण". Applied and Computational Harmonic Analysis. 40 (2): 260–291. arXiv:1307.5708. doi:10.1016/j.acha.2015.02.005. ISSN 1063-5203.
↑ Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (July 2017). "Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes]". IEEE Signal Processing Magazine (in English). 34 (4): 176–182. Bibcode:2017ISPM...34..176S. doi:10.1109/msp.2017.2696572. ISSN 1053-5888.
↑ Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (September 2016). "स्पेक्ट्रल ग्राफ वेवलेट्स और फ़िल्टर बैंक कम सन्निकटन त्रुटि के साथ". IEEE Transactions on Signal and Information Processing over Networks (in English). 2 (3): 230–245. doi:10.1109/tsipn.2016.2581303. ISSN 2373-776X.
↑ Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (2016-11-15). "रेखांकन पर सिग्नल-अनुकूलित टाइट फ्रेम". IEEE Transactions on Signal Processing (in English). 64 (22): 6017–6029. Bibcode:2016ITSP...64.6017B. doi:10.1109/tsp.2016.2591513. ISSN 1053-587X.

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]

[1] Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.

[2] Weisstein, Eric W. "Cospectral Graphs". MathWorld.

[3] Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices", Journal of Chemical Information and Modeling, 34 (2): 428–431, doi:10.1021/ci00018a033.

[FOOTNOTESchwenk1973275–307-4] Schwenk (1973), pp. 275–307.

[5] Godsil, Chris (November 7, 2007). "Are Almost All Graphs Cospectral?" (PDF).

[6] Sunada, Toshikazu (1985), "Riemannian coverings and isospectral manifolds", Ann. of Math., 121 (1): 169–186, doi:10.2307/1971195, JSTOR 1971195.

[7] Brouwer & Haemers 2011

[8] Definition 2.1 in Hoory, Linial & Wigderson (2006)

[9] J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.

[FOOTNOTEAlonSpencer2011-10] Alon & Spencer 2011.

[11] Theorem 2.4 in Hoory, Linial & Wigderson (2006)

[chung-12] 12.0 ^12.1 ^12.2 Chung, Fan (1997). American Mathematical Society (ed.). स्पेक्ट्रल ग्राफ थ्योरी. Providence, R. I. ISBN 0821803158. MR 1421568[first 4 chapters are available in the website]{{cite book}}: CS1 maint: postscript (link)

[13] Godsil, Chris (May 2009). "Erdős-Ko-Rado Theorems" (PDF).

[14] Godsil, C. D.; Meagher, Karen (2016). Erdős-Ko-Rado theorems : algebraic approaches. Cambridge, United Kingdom. ISBN 9781107128446. OCLC 935456305.{{cite book}}: CS1 maint: location missing publisher (link)

[cvet2-15] 15.0 ^15.1 Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1

[16] Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)

[17] Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणाम. Annals of Discrete mathematics. ISBN 0-444-70361-6.

[18] Sunada, Toshikazu (2008), "Discrete geometric analysis", Proceedings of Symposia in Pure Mathematics, 77: 51–86, doi:10.1090/pspum/077/2459864, ISBN 9780821844717.

[19] Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre (March 2016). "रेखांकन पर शीर्ष-आवृत्ति विश्लेषण". Applied and Computational Harmonic Analysis. 40 (2): 260–291. arXiv:1307.5708. doi:10.1016/j.acha.2015.02.005. ISSN 1063-5203.

[20] Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (July 2017). "Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes]". IEEE Signal Processing Magazine (in English). 34 (4): 176–182. Bibcode:2017ISPM...34..176S. doi:10.1109/msp.2017.2696572. ISSN 1053-5888.

[21] Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (September 2016). "स्पेक्ट्रल ग्राफ वेवलेट्स और फ़िल्टर बैंक कम सन्निकटन त्रुटि के साथ". IEEE Transactions on Signal and Information Processing over Networks (in English). 2 (3): 230–245. doi:10.1109/tsipn.2016.2581303. ISSN 2373-776X.

[22] Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (2016-11-15). "रेखांकन पर सिग्नल-अनुकूलित टाइट फ्रेम". IEEE Transactions on Signal Processing (in English). 64 (22): 6017–6029. Bibcode:2016ITSP...64.6017B. doi:10.1109/tsp.2016.2591513. ISSN 1053-587X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 46: / Line 46: @@
 == चीजर असमानता ==
-रीमैनियन ज्यामिति से प्रसिद्ध चीगर की असमानता में लाप्लासियन मैट्रिक्स से जुड़ा एक असतत एनालॉग है; यह संभवतः स्पेक्ट्रल ग्राफ सिद्धांत में सबसे महत्वपूर्ण प्रमेय है और एल्गोरिथम अनुप्रयोगों में सबसे उपयोगी तथ्यों में से एक है। यह लाप्लासियन के दूसरे अभिलक्षणिक मान के माध्यम से एक ग्राफ के सबसे कम कटौती का अनुमान लगाता है।
+रीमैनियन ज्यामिति से प्रसिद्ध चीजर की असमानता में लाप्लासियन मैट्रिक्स से जुड़ा एक असतत एनालॉग है; यह संभवतः स्पेक्ट्रल ग्राफ सिद्धांत में सबसे महत्वपूर्ण प्रमेय है और एल्गोरिथम अनुप्रयोगों में सबसे उपयोगी तथ्यों में से एक है। यह लाप्लासियन के दूसरे अभिलक्षणिक मान के माध्यम से एक ग्राफ के सबसे कम कटौती का अनुमान लगाता है।
 === चीजर स्थिरांक ===
 {{main|चीजर स्थिरांक (ग्राफ सिद्धांत)}}
-किसी ग्राफ़ का '''चीगर स्थिरांक''' ('''चीजर संख्या''' या '''समपरिमापीय संख्या''' भी) एक संख्यात्मक माप है कि ग्राफ़ में अड़चन है या नहीं। अड़चन के एक उपाय के रूप में चीजर स्थिरांक कई क्षेत्रों में बहुत रुचि रखता है: उदाहरण के लिए, अच्छी तरह से जुड़े [[ कम्प्यूटर नेट्वर्किंग ]], [[ पुथल ]] और [[ ज्यामितीय टोपोलॉजी ]] का निर्माण। कम-आयामी टोपोलॉजी (विशेष रूप से, [[अतिशयोक्तिपूर्ण ज्यामिति]] 3-[[कई गुना]] का अध्ययन)।
+किसी ग्राफ़ का '''चीजर स्थिरांक''' ('''चीजर संख्या''' या '''समपरिमापीय संख्या''' भी) एक संख्यात्मक माप है कि ग्राफ़ में <nowiki>''</nowiki>अवरोध<nowiki>''</nowiki> है या नहीं। <nowiki>''</nowiki>रुकावट<nowiki>''</nowiki> के एक उपाय के रूप में चीजर स्थिरांक कई क्षेत्रों में बहुत रुचि रखता है: उदाहरण के लिए, अच्छी तरह से जुड़े [[ कम्प्यूटर नेट्वर्किंग |कम्प्यूटर नेट्वर्किंग]], [[ पुथल |कार्ड शफलिंग]] और [[ ज्यामितीय टोपोलॉजी |निम्न-आयामी टोपोलॉजी]] का निर्माण (विशेष रूप से, [[अतिशयोक्तिपूर्ण ज्यामिति|अतिपरवलयिक ज्यामिति]] 3-[[कई गुना|बहुविध]] का अध्ययन)।
-अधिक औपचारिक रूप से, ''n'' कोने पर एक ग्राफ ''G'' के चीजर स्थिरांक ''h''(''G'') को इस रूप में परिभाषित किया गया है
+अधिक औपचारिक रूप से, ''n'' शिरोबिंदु पर एक ग्राफ ''G'' के चीजर स्थिरांक ''h''(''G'') को इस रूप में परिभाषित किया गया है
 : <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|},</math>
-जहां न्यूनतम अधिकतम n/2 कोने के सभी गैर-खाली सेट S पर है और ∂(S) S की किनारे की सीमा है, यानी किनारों का सेट S में ठीक एक समापन बिंदु के साथ है।<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+जहां न्यूनतम n/2 कोने के सभी गैर-खाली समूह S पर है और ∂(S) S की किनारे की सीमा है, यानी किनारों का समूह S में ठीक एक समापन बिंदु के साथ है।<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
 === चीजर असमानता ===
-जब ग्राफ जी डी-नियमित होता है, तो एच (जी) और वर्णक्रमीय अंतराल डी - λ के बीच संबंध होता है<sub>2</sub> जी की। डोडिज़ुक के कारण एक असमानता<ref>J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.</ref> और स्वतंत्र रूप से [[ सावधान अलोन ]] और [[विटाली मिलमैन]]{{Sfn|Alon|Spencer|2011}} बताता है<ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+जब ग्राफ ''G'' ''d''-नियमित होता है, तो ''h''(''G'') और वर्णक्रमीय अंतराल ''d'' − λ<sub>2</sub> के बीच एक संबंध होता है। डोडिज़ुक <ref>J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.</ref> और स्वतंत्र रूप से [[ सावधान अलोन |एलोन]] और [[विटाली मिलमैन]]{{Sfn|Alon|Spencer|2011}} के कारण एक असमानता बताती है कि<ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
 : <math>\frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>
-यह असमानता मार्कोव श्रृंखलाओं के लिए [[चीजर बाध्य]] से निकटता से संबंधित है और इसे चीगर कॉन्सटेंट#चीगर.27s असमानता|रीमैनियन ज्यामिति में चीगर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।
+यह असमानता मार्कोव श्रृंखलाओं के लिए [[चीजर बाध्य]] से निकटता से संबंधित है और इसे चीजर रीमैनियन ज्यामिति में चीजर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।
 सामान्य रूप से जुड़े ग्राफ़ के लिए जो आवश्यक रूप से नियमित नहीं हैं, चुंग द्वारा एक वैकल्पिक असमानता दी गई है<ref name=chung>{{cite book |last =Chung |first1 =Fan |author-link =Fan Chung |year =1997 |title =स्पेक्ट्रल ग्राफ थ्योरी|isbn =0821803158 |mr =1421568 |url =http://www.math.ucsd.edu/~fan/research/revised.html |postscript = [first 4 chapters are available in the website] |editor =American Mathematical Society |publisher =Providence, R. I.}}</ref>{{rp|35}}
 :<math> \frac{1}{2} {\lambda} \le {\mathbf h}(G)  \le \sqrt{2 \lambda},</math>
-कहाँ <math>\lambda</math> सामान्यीकृत लाप्लासियन का कम से कम गैर-तुच्छ अभिलक्षणिक मान है, और <math>{\mathbf h}(G)</math> (सामान्यीकृत) चीगर स्थिरांक है
+जहाँ <math>\lambda</math> सामान्यीकृत लाप्लासियन का कम से कम गैर-तुच्छ अभिलक्षणिक मान है, और <math>{\mathbf h}(G)</math> (सामान्यीकृत) चीजर स्थिरांक है
 :  <math> {\mathbf h}(G) = \min_{\emptyset \not =S\subset V(G)}\frac{|\partial(S)|}{\min({\mathrm{vol}}(S), {\mathrm{vol}}(\bar{S}))}</math>
-कहाँ <math>{\mathrm{vol}}(Y)</math> में शीर्षों की डिग्री का योग है <math>Y</math>.
+जहाँ <math>{\mathrm{vol}}(Y)</math> <math>Y</math> में शीर्षों के अंशो का योग है।
 == हॉफमैन-डेल्सर्ट असमानता ==
-मूल रूप से एलन जे हॉफमैन और फिलिप डेल्सर्ट के कारण नियमित ग्राफ में [[स्वतंत्र सेट (ग्राफ सिद्धांत)]] के लिए एक ईगेनवैल्यू बाध्य है।<ref>{{Cite web|url=https://www.math.uwaterloo.ca/~cgodsil/pdfs/ekrs-clg.pdf|title=Erdős-Ko-Rado Theorems|last=Godsil|first=Chris|date=May 2009}}</ref>
+मूल रूप से एलन जे हॉफमैन और फिलिप डेल्सर्ट के कारण नियमित ग्राफ में [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र समूह]] के लिए एक अभिलक्षणिक मान बाध्य है।<ref>{{Cite web|url=https://www.math.uwaterloo.ca/~cgodsil/pdfs/ekrs-clg.pdf|title=Erdős-Ko-Rado Theorems|last=Godsil|first=Chris|date=May 2009}}</ref>
-लगता है कि <math>G</math> एक है <math>k</math>-नियमित ग्राफ पर <math>n</math> कम से कम अभिलक्षणिक मान वाले कोने <math>\lambda_{\mathrm{min}}</math>. तब:<math display="block">\alpha(G) \leq \frac{n}{1 - \frac{k}{\lambda_{\mathrm{min}}}}</math>कहाँ <math>\alpha(G)</math> इसकी [[स्वतंत्रता संख्या]] को दर्शाता है।
+मान लीजिए है कि <math>G</math> एक कम से कम अभिलक्षणिक मान वाले <math>\lambda_{\mathrm{min}}</math>के साथ  <math>n</math> कोने पर  एक <math>k</math>-नियमित ग्राफ है। तब:<math display="block">\alpha(G) \leq \frac{n}{1 - \frac{k}{\lambda_{\mathrm{min}}}}</math>जहाँ  <math>\alpha(G)</math> इसकी [[स्वतंत्रता संख्या|स्वतंत्र संख्या]] को दर्शाता है।
-इस सीमा को स्थापित करने के लिए लागू किया गया है उदा। एर्दोस-को-राडो प्रमेय के बीजगणितीय प्रमाण और [[परिमित क्षेत्र]]ों पर उप-स्थानों के परिवारों को प्रतिच्छेद करने के लिए इसका एनालॉग।<ref>{{Cite book|title=Erdős-Ko-Rado theorems : algebraic approaches|last1=Godsil|first1=C. D.|last2=Meagher|first2=Karen|isbn=9781107128446|location=Cambridge, United Kingdom|oclc=935456305|year = 2016}}</ref>
+इस सीमा को स्थापित करने के लिए लागू किया गया है उदा. एर्दोस-को-राडो प्रमेय के बीजगणितीय प्रमाण और [[परिमित क्षेत्र|परिमित क्षेत्रों]] पर उप-स्थानों के परिवारों को प्रतिच्छेद करने के लिए इसके रेखीय।<ref>{{Cite book|title=Erdős-Ko-Rado theorems : algebraic approaches|last1=Godsil|first1=C. D.|last2=Meagher|first2=Karen|isbn=9781107128446|location=Cambridge, United Kingdom|oclc=935456305|year = 2016}}</ref>
-सामान्य रेखांकन के लिए जो आवश्यक रूप से नियमित नहीं हैं, स्वतंत्रता संख्या के लिए एक समान ऊपरी सीमा अधिकतम अभिलक्षणिक मान का उपयोग करके प्राप्त की जा सकती है
-<math> \lambda'_{max}</math> सामान्यीकृत लाप्लासियन का<ref name=chung/>का <math>G</math>:
+सामान्य ग्राफ के लिए जो आवश्यक रूप से नियमित नहीं हैं, स्वतंत्र संख्या के लिए एक समान ऊपरी सीमा <math>G</math> के सामान्यीकृत लाप्लासियन <ref name="chung" /> के अधिकतम अभिलक्षणिक मान <math> \lambda'_{max}</math> का उपयोग करके प्राप्त की जा सकती है:
 <math display="block">\alpha(G) \leq n (1-\frac {1}{\lambda'_{\mathrm{max}}}) \frac {\mathrm{max deg}}{\mathrm{min deg}}
 </math>
-कहाँ <math>{\mathrm{max deg}}</math> और <math>{\mathrm{min deg}}</math> में अधिकतम और न्यूनतम डिग्री को निरूपित करें <math>G</math>, क्रमश। यह अधिक सामान्य असमानता का परिणाम है (पृष्ठ 109 इंच
+जहाँ  <math>{\mathrm{max deg}}</math> और <math>{\mathrm{min deg}}</math> <math>G</math> में क्रमशः अधिकतम और न्यूनतम डिग्री दर्शाते हैं। यह अधिक सामान्य असमानता का परिणाम है (पृष्ठ 109 में<ref name="chung" />):
-<ref name=chung/>):
 <math display="block">{\mathrm{vol}}(X) \leq  (1-\frac {1}{\lambda'_{\mathrm{max}}}) {\mathrm{vol}}(V(G))
-</math> कहाँ <math>X</math> वर्टिकल और का एक स्वतंत्र सेट है <math>{\mathrm{vol}}(Y)</math> में शीर्षों की डिग्री के योग को दर्शाता है <math>Y</math> .
+</math> जहाँ <math>X</math> शीर्षों का एक स्वतंत्र समुच्चय है और <math>{\mathrm{vol}}(Y)</math> <math>Y</math> में शीर्षों की डिग्री के योग को दर्शाता है।
 == ऐतिहासिक रूपरेखा ==
-स्पेक्ट्रल ग्राफ सिद्धांत 1950 और 1960 के दशक में उभरा। ग्राफ के संरचनात्मक और वर्णक्रमीय गुणों के बीच संबंध पर ग्राफ सिद्धांत अनुसंधान के अलावा, एक अन्य प्रमुख स्रोत [[क्वांटम रसायन]] विज्ञान में शोध था, लेकिन काम की इन दो पंक्तियों के बीच संबंध बहुत बाद तक खोजे नहीं गए थे।<ref name= cvet2>''Eigenspaces of Graphs'', by [[Dragoš Cvetković]], Peter Rowlinson, Slobodan Simić (1997) {{isbn|0-521-57352-1}}</ref> 1980 का मोनोग्राफ स्पेक्ट्रा ऑफ़ ग्राफ़<ref>Dragoš M. Cvetković, Michael Doob, [[Horst Sachs]], ''Spectra of Graphs'' (1980)</ref> Cvetković द्वारा, Doob, और Sachs ने इस क्षेत्र में आज तक के लगभग सभी शोधों को संक्षेप में प्रस्तुत किया है। 1988 में इसे ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणामों के सर्वेक्षण द्वारा अद्यतन किया गया था।<ref>{{cite book|first1=Dragoš M.|last1=Cvetković |first2=Michael |last2=Doob |first3=Ivan |last3=Gutman |first4=A. |last4=Torgasev |title=ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणाम|series=Annals of Discrete mathematics |number=36 |year=1988 |isbn=0-444-70361-6 |url=http://www.sciencedirect.com/science/bookseries/01675060/36}}</ref> स्पेक्ट्रा ऑफ़ ग्राफ़्स (1995) के तीसरे संस्करण में इस विषय में हाल के योगदानों का सारांश सम्मिलित है।<ref name= cvet2/>2000 के दशक में [[तोशिवा यह रेत है]] द्वारा निर्मित और विकसित असतत ज्यामितीय विश्लेषण भारित ग्राफ़ से जुड़े असतत लाप्लासियन के संदर्भ में वर्णक्रमीय ग्राफ सिद्धांत से संबंधित है,<ref>{{citation | last = Sunada | first = Toshikazu | journal = Proceedings of Symposia in Pure Mathematics | pages = 51–86 | title =  Discrete geometric analysis | volume = 77 | year = 2008| doi = 10.1090/pspum/077/2459864 | isbn = 9780821844717 }}.</ref> और स्पेक्ट्रल आकार विश्लेषण सहित विभिन्न क्षेत्रों में आवेदन पाता है। हाल के वर्षों में, वर्णक्रमीय ग्राफ सिद्धांत का विस्तार कई वास्तविक जीवन के अनुप्रयोगों में प्रायः सामने आने वाले वर्टेक्स-अलग-अलग ग्राफ़ तक हो गया है।<ref>{{Cite journal|last=Shuman|first=David I|last2=Ricaud|first2=Benjamin|last3=Vandergheynst|first3=Pierre|date=March 2016|title=रेखांकन पर शीर्ष-आवृत्ति विश्लेषण|journal=Applied and Computational Harmonic Analysis|volume=40|issue=2|pages=260–291|doi=10.1016/j.acha.2015.02.005|issn=1063-5203|arxiv=1307.5708}}</ref><ref>{{Cite journal|last=Stankovic|first=Ljubisa|last2=Dakovic|first2=Milos|last3=Sejdic|first3=Ervin|date=July 2017|title=Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes]|journal=IEEE Signal Processing Magazine|language=en-US|volume=34|issue=4|pages=176–182|doi=10.1109/msp.2017.2696572|issn=1053-5888|bibcode=2017ISPM...34..176S}}</ref><ref>{{Cite journal|last=Sakiyama|first=Akie|last2=Watanabe|first2=Kana|last3=Tanaka|first3=Yuichi|date=September 2016|title=स्पेक्ट्रल ग्राफ वेवलेट्स और फ़िल्टर बैंक कम सन्निकटन त्रुटि के साथ|journal=IEEE Transactions on Signal and Information Processing over Networks|language=en-US|volume=2|issue=3|pages=230–245|doi=10.1109/tsipn.2016.2581303|issn=2373-776X}}</ref><ref>{{Cite journal|last=Behjat|first=Hamid|last2=Richter|first2=Ulrike|last3=Van De Ville|first3=Dimitri|last4=Sornmo|first4=Leif|date=2016-11-15|title=रेखांकन पर सिग्नल-अनुकूलित टाइट फ्रेम|journal=IEEE Transactions on Signal Processing|language=en-US|volume=64|issue=22|pages=6017–6029|doi=10.1109/tsp.2016.2591513|issn=1053-587X|bibcode=2016ITSP...64.6017B|url=http://infoscience.epfl.ch/record/223159}}</ref>
+स्पेक्ट्रल ग्राफ सिद्धांत 1950 और 1960 के दशक में उभरा था। ग्राफ के संरचनात्मक और वर्णक्रमीय गुणों के बीच संबंध पर ग्राफ सैद्धांतिक शोध के अलावा, एक अन्य प्रमुख स्रोत [[क्वांटम रसायन]] विज्ञान में शोध था, लेकिन काम की इन दो पंक्तियों के बीच संबंध बहुत बाद तक खोजे नहीं गए थे।<ref name= cvet2>''Eigenspaces of Graphs'', by [[Dragoš Cvetković]], Peter Rowlinson, Slobodan Simić (1997) {{isbn|0-521-57352-1}}</ref> सीवेटकोविच, डूब और साक्स द्वारा 1980 के मोनोग्राफ स्पेक्ट्रा ऑफ़ ग्राफ़्स<ref>Dragoš M. Cvetković, Michael Doob, [[Horst Sachs]], ''Spectra of Graphs'' (1980)</ref> में इस क्षेत्र में आज तक के लगभग सभी शोधों को संक्षेप में प्रस्तुत किया है। 1988 में इसे ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणामों के सर्वेक्षण द्वारा अद्यतन किया गया था।<ref>{{cite book|first1=Dragoš M.|last1=Cvetković |first2=Michael |last2=Doob |first3=Ivan |last3=Gutman |first4=A. |last4=Torgasev |title=ग्राफ स्पेक्ट्रा के सिद्धांत में हाल के परिणाम|series=Annals of Discrete mathematics |number=36 |year=1988 |isbn=0-444-70361-6 |url=http://www.sciencedirect.com/science/bookseries/01675060/36}}</ref> स्पेक्ट्रा ऑफ़ ग्राफ़्स (1995) के तीसरे संस्करण में इस विषय में हाल के योगदानों का सारांश सम्मिलित है।<ref name= cvet2/>2000 के दशक में [[तोशिवा यह रेत है|तोशिकाज़ू सुनदा]] द्वारा निर्मित और विकसित असतत ज्यामितीय विश्लेषण भारित ग्राफ़ से जुड़े असतत लाप्लासियन के संदर्भ में वर्णक्रमीय ग्राफ सिद्धांत से संबंधित है,<ref>{{citation | last = Sunada | first = Toshikazu | journal = Proceedings of Symposia in Pure Mathematics | pages = 51–86 | title =  Discrete geometric analysis | volume = 77 | year = 2008| doi = 10.1090/pspum/077/2459864 | isbn = 9780821844717 }}.</ref> और स्पेक्ट्रल आकार विश्लेषण सहित विभिन्न क्षेत्रों में आवेदन पाता है।हाल के वर्षों में, वर्णक्रमीय ग्राफ सिद्धांत का विस्तार वर्टेक्स-विभिन्न ग्राफों तक हो गया है, जो प्रायः कई वास्तविक जीवन अनुप्रयोगों में सामने आते हैं।<ref>{{Cite journal|last=Shuman|first=David I|last2=Ricaud|first2=Benjamin|last3=Vandergheynst|first3=Pierre|date=March 2016|title=रेखांकन पर शीर्ष-आवृत्ति विश्लेषण|journal=Applied and Computational Harmonic Analysis|volume=40|issue=2|pages=260–291|doi=10.1016/j.acha.2015.02.005|issn=1063-5203|arxiv=1307.5708}}</ref><ref>{{Cite journal|last=Stankovic|first=Ljubisa|last2=Dakovic|first2=Milos|last3=Sejdic|first3=Ervin|date=July 2017|title=Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes]|journal=IEEE Signal Processing Magazine|language=en-US|volume=34|issue=4|pages=176–182|doi=10.1109/msp.2017.2696572|issn=1053-5888|bibcode=2017ISPM...34..176S}}</ref><ref>{{Cite journal|last=Sakiyama|first=Akie|last2=Watanabe|first2=Kana|last3=Tanaka|first3=Yuichi|date=September 2016|title=स्पेक्ट्रल ग्राफ वेवलेट्स और फ़िल्टर बैंक कम सन्निकटन त्रुटि के साथ|journal=IEEE Transactions on Signal and Information Processing over Networks|language=en-US|volume=2|issue=3|pages=230–245|doi=10.1109/tsipn.2016.2581303|issn=2373-776X}}</ref><ref>{{Cite journal|last=Behjat|first=Hamid|last2=Richter|first2=Ulrike|last3=Van De Ville|first3=Dimitri|last4=Sornmo|first4=Leif|date=2016-11-15|title=रेखांकन पर सिग्नल-अनुकूलित टाइट फ्रेम|journal=IEEE Transactions on Signal Processing|language=en-US|volume=64|issue=22|pages=6017–6029|doi=10.1109/tsp.2016.2591513|issn=1053-587X|bibcode=2016ITSP...64.6017B|url=http://infoscience.epfl.ch/record/223159}}</ref>
@@ Line 111: / Line 110: @@
 * {{cite web| first1=Daniel |last1=Spielman | url=http://www.cs.yale.edu/homes/spielman/eigs/ |title=Spectral Graph Theory and its Applications |year=2004}} [course page and lecture notes]
-{{DEFAULTSORT:Spectral Graph Theory}}[[Category: बीजगणितीय ग्राफ सिद्धांत|*]] [[Category: स्पेक्ट्रल सिद्धांत|*]]
+{{DEFAULTSORT:Spectral Graph Theory}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Spectral Graph Theory]]
-[[Category:Created On 08/05/2023]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:CS1 maint|Spectral Graph Theory]]
+[[Category:Created On 08/05/2023|Spectral Graph Theory]]
+[[Category:Lua-based templates|Spectral Graph Theory]]
+[[Category:Machine Translated Page|Spectral Graph Theory]]
+[[Category:Pages with script errors|Spectral Graph Theory]]
+[[Category:Templates Vigyan Ready|Spectral Graph Theory]]
+[[Category:Templates that add a tracking category|Spectral Graph Theory]]
+[[Category:Templates that generate short descriptions|Spectral Graph Theory]]
+[[Category:Templates using TemplateData|Spectral Graph Theory]]
+[[Category:बीजगणितीय ग्राफ सिद्धांत|*]]
+[[Category:स्पेक्ट्रल सिद्धांत|*]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 17:42, 17 May 2023

Contents