दो-ग्राफ: Difference between revisions

From Vigyanwiki
(TEXT)
(TEXT)
Line 8: Line 8:
यह दो-आलेख़ एक नियमित दो-आलेख़ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो त्रिगुण में एक साथ दिखाई देती है।
यह दो-आलेख़ एक नियमित दो-आलेख़ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो त्रिगुण में एक साथ दिखाई देती है।


एक साधारण आलेख ''G'' = (''V'',''E'') को देखते हुए, त्रिभुज समुच्चय ''V'' के त्रिगुण का समुच्चय जिसका प्रेरित उपआलेख में किनारों की विषम संख्या होती है, समुच्चय ''V'' पर दो-आलेख़ बनाता है। प्रत्येक दो-आलेख़ को इस तरह से दर्शाया जा सकता है।<ref>{{harvnb|Colburn|Dinitz|2007|loc=p. 876, Remark 13.2}}</ref> इस उदाहरण को एक साधारण आलेख से दो-आलेख़ के मानक निर्माण के रूप में जाना जाता है।
एक साधारण आलेख ''G'' = (''V'',''E'') को देखते हुए, शीर्ष समुच्चय ''V'' के त्रिगुण का समुच्चय जिसका प्रेरित उपआलेख में किनारों की विषम संख्या होती है, समुच्चय ''V'' पर दो-आलेख़ बनाता है। प्रत्येक दो-आलेख़ को इस तरह से दर्शाया जा सकता है।<ref>{{harvnb|Colburn|Dinitz|2007|loc=p. 876, Remark 13.2}}</ref> इस उदाहरण को एक साधारण आलेख से दो-आलेख़ के मानक निर्माण के रूप में जाना जाता है।


अधिक सम्मिश्र उदाहरण के रूप में, ''T'' को कोर समुच्चय ''E'' के साथ एक ट्री होता है। ''E'' के सभी त्रिगुणों का समुच्चय जो ''T'' के पथ में सम्मिलित नहीं हैं, समुच्चय ''E'' पर दो-आलेख़ बनाते हैं।<ref>{{citation|first=P.J.|last=Cameron|title=Two-graphs and trees|journal=Discrete Mathematics|volume=127|year=1994|pages=63-74}} cited in {{harvnb|Colburn|Dinitz|2007|loc=p. 876, Construction 13.12}}</ref>
अधिक सम्मिश्र उदाहरण के रूप में, ''T'' को कोर समुच्चय ''E'' के साथ एक ट्री होता है। ''E'' के सभी त्रिगुणों का समुच्चय जो ''T'' के पथ में सम्मिलित नहीं हैं, समुच्चय ''E'' पर दो-आलेख़ बनाते हैं।<ref>{{citation|first=P.J.|last=Cameron|title=Two-graphs and trees|journal=Discrete Mathematics|volume=127|year=1994|pages=63-74}} cited in {{harvnb|Colburn|Dinitz|2007|loc=p. 876, Construction 13.12}}</ref>
Line 14: Line 14:
[[file:Xyswitch.svg|thumb|आलेख़ में {X, Y} स्विच करना]]एक दो-आलेख़ के स्विचन वर्ग के समान है और [[हस्ताक्षरित ग्राफ|हस्ताक्षरित पूर्ण]] आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है।
[[file:Xyswitch.svg|thumb|आलेख़ में {X, Y} स्विच करना]]एक दो-आलेख़ के स्विचन वर्ग के समान है और [[हस्ताक्षरित ग्राफ|हस्ताक्षरित पूर्ण]] आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है।


एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि प्रत्येक जोड़ी के शीर्ष की आसन्नता को प्रतिलोम देना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार एज समुच्चय को बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट और एक असन्निकट जोड़ी बन जाए समीप हो जाता है। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के तहत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग द्वारा पेश किया गया था {{harvtxt|van Lint|Seidel|1966}} और सीडेल द्वारा विकसित; इसे आलेख़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित आलेख़ के स्विचिंग से अलग करने के लिए।
एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि शीर्ष के प्रत्येक जोड़े की निकटता को प्रतिलोम देना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार किनारे का समुच्चय बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट हो जाए और एक असन्निकट जोड़ी सन्निकट हो जाए। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के अंतर्गत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग को {{harvtxt|वैन लिंट|सेडेल|1966}} द्वारा प्रस्तावित किया गया था और सीडेल द्वारा विकसित किया गया था; इसे आलेख़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित आलेख़ के स्विचिंग से अलग करने के लिए किया गया है।


ऊपर दिए गए सरल आलेख़ से दो-आलेख़ के मानक निर्माण में, दो आलेख़ समान दो-आलेख़ उत्पन्न करेंगे यदि और केवल यदि वे स्विचिंग के समतुल्य हैं, अर्थात वे एक ही स्विचिंग वर्ग में हैं।
ऊपर दिए गए सरल आलेख़ से दो-आलेख़ के मानक निर्माण में, दो आलेख़ समान दो-आलेख़ उत्पन्न करेंगे यदि और केवल यदि वे स्विचिंग के समतुल्य हैं, अर्थात वे एक ही स्विचिंग वर्ग में हैं।


मान लीजिए कि 'X' समुच्चय पर Γ एक दो-आलेख़ है। ''X'' के किसी भी तत्व ''x'' के लिए, एक आलेख Γ परिभाषित करें<sub>''x''</sub> त्रिभुज समुच्चय X के साथ शीर्ष y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस आलेख में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण आलेख जी दिया गया है, एक नए तत्व एक्स को जी के शीर्षों के समुच्चय से जोड़ता है, उसी किनारे के समुच्चय को बनाए रखता है, और उपरोक्त मानक निर्माण को लागू करता है।<ref>{{harvnb|Cameron|van Lint|1991|loc=pp. 58-59}}</ref> एक आलेख़ जी के लिए एक ही त्रिभुज समुच्चय पर एक हस्ताक्षरित पूर्ण आलेख़ Σ से मेल खाता है, जिसका किनारों को जी में नहीं तो सकारात्मक और सकारात्मक पर हस्ताक्षर किए गए हैं। इसके विपरीत, जी Σ का सबआलेख है जिसमें सभी कोने और सभी नकारात्मक किनारे सम्मिलित हैं। जी के दो-आलेख़ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के त्रिगुण के समुच्चय के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण आलेख़ समान दो-आलेख़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।
अनुमान कि Γ समुच्चय X पर एक दो-आलेख़ है। ''X'' के किसी भी तत्व ''x'' के लिए, एक आलेख Γ<sub>''x''</sub> को शीर्ष समुच्चय X के साथ परिभाषित करें जिसमें कोने y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस आलेख में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण आलेख ''G'' दिया गया है, एक नए तत्व ''x'' को ''G'' के शीर्षों के समुच्चय से जोड़ता है, उसी किनारे के समुच्चय को बनाए रखता है, और उपरोक्त मानक निर्माण को उपयोजित करता है।<ref>{{harvnb|Cameron|van Lint|1991|loc=pp. 58-59}}</ref>  


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


== निकटता मैट्रिक्स ==
''G'' और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक आलेख ''H'' और उसके संबंधित पूर्ण आलेख पर हस्ताक्षर किए जाते हैं।


दो-आलेख़ का आसन्न मैट्रिक्स संबंधित हस्ताक्षरित पूर्ण आलेख़ का हस्ताक्षरित आलेख़ है; इस प्रकार यह [[सममित मैट्रिक्स]] है, विकर्ण पर शून्य है, और विकर्ण से प्रविष्टियाँ ±1 हैं। यदि ''G'' हस्ताक्षरित पूर्ण आलेख़ Σ के संगत आलेख़ है, तो इस मैट्रिक्स को (0, -1, 1)-आसन्नता मैट्रिक्स या ''G'' का सीडल आसन्न मैट्रिक्स कहा जाता है। सेडेल मैट्रिक्स में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और गैर-निकटवर्ती शीर्षों के लिए +1 प्रविष्टियाँ हैं।
== आसन्नता आव्यूह ==


यदि आलेख़ ''G'' और ''H'' एक ही स्विचिंग वर्ग में हैं, तो ''G'' और ''H'' के दो सेडेल आसन्न मैट्रिक्स के eigenvalues ​​​​के मल्टीसमुच्चय मेल खाते हैं क्योंकि मेट्रिसेस समान हैं।<ref>{{harvnb|Cameron|van Lint|1991|loc=p. 61}}</ref>
दो-आलेख़ का आसन्न आव्यूह संबंधित हस्ताक्षरित पूर्ण आलेख़ का आसन्न आलेख़ है; इस प्रकार यह [[सममित मैट्रिक्स|सममित]] है, विकर्ण पर शून्य है, और विकर्ण से ±1 प्रविष्टियाँ हैं। यदि ''G'' हस्ताक्षरित पूर्ण आलेख़ Σ का पुर्ण आलेख़ है, तो इस आव्यूह को (0, -1, 1)-आसन्नता आव्यूह या ''G'' का सीडल आसन्न आव्यूह कहा जाता है। सेडेल आव्यूह में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और असन्निकट शीर्षों के लिए +1 प्रविष्टियाँ हैं।
एक समुच्चय वी पर एक दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न मैट्रिक्स में केवल दो अलग-अलग ईजेनवैल्यू और ईजेनवेक्टर ρ हैं<sub>1</sub> > 0 > प<sub>2</sub> कहते हैं, जहां ρ<sub>1</sub>ρ<sub>2</sub> = 1 - |वी|।<ref>{{harvnb|Colburn|Dinitz|2007|loc=p. 878  #13.24}}</ref>
 
यदि आलेख़ ''G'' और ''H'' एक ही स्विचिंग वर्ग में हैं, तो ''G'' और ''H'' के दो सेडेल आसन्न आव्यूह के अभिलक्षणिक मानों के बहुसमुच्चय अनुरूप हैं क्योंकि मेट्रिसेस समान हैं।<ref>{{harvnb|Cameron|van Lint|1991|loc=p. 61}}</ref>
 
एक समुच्चय ''V'' पर दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न आव्यूह में केवल दो अलग-अलग अभिलक्षणिक मान और ईजेनवेक्टर ρ<sub>1</sub> > 0 > ρ<sub>2</sub> कहते हैं, जहां ρ<sub>1</sub>ρ<sub>2</sub> = 1 - |''V''| हैं।<ref>{{harvnb|Colburn|Dinitz|2007|loc=p. 878  #13.24}}</ref>
== समकोण रेखाएँ ==
== समकोण रेखाएँ ==
{{main|Equiangular lines}}
{{main|समकोण रेखाएँ}}
 
प्रत्येक दो-आलेख़ कुछ आयामी [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन समष्टि]] में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। n शीर्षों पर दो आलेख से निर्मित रेखाओं का समुच्चय इस प्रकार प्राप्त होता है। अनुमान -ρ दो-आलेख़ के सेडेल आसन्न आव्यूह, ''A'' के सबसे लघुतम अभिलक्षणिक मान है और अपेक्षित इसकी बहुलता n - d है। तब आव्यूह {{nobreak|1=ρ''I'' + ''A''}} श्रेणी d का सकारात्मक अर्ध-निश्चित है और इस प्रकार यूक्लिडियन ''d''-समष्टि में n सदिश के आंतरिक उत्पादों के [[ग्राम मैट्रिक्स|ग्राम आव्यूह]] के रूप में प्रदर्शित किया जा सकता है। जैसा कि इन सदिशों के समान प्रतिमान (अर्थात्, <math>\sqrt{\rho}</math>) और आपसी आंतरिक उत्पाद ±1 हैं, उनके द्वारा विस्तरित n रेखाओं की कोई भी जोड़ी समान कोण φ में मिलती है जहाँ cos φ = 1/ρ है। इसके विपरीत, एक यूक्लिडियन समष्टि में गैर-लंबकोणिक समकोणीय रेखाओं का कोई भी समुच्चय दो-आलेख़ को वृद्धि दे सकता है (निर्माण के लिए समान रेखाएं देखें)।<ref>{{harvnb|van Lint|Seidel|1966}}</ref>


प्रत्येक दो-आलेख़ कुछ आयामी [[यूक्लिडियन अंतरिक्ष]] में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। n शीर्षों पर दो आलेख से निर्मित रेखाओं का समुच्चय इस प्रकार प्राप्त होता है। चलो -ρ दो-आलेख़ के सेडेल आसन्न मैट्रिक्स, ए के सबसे छोटे आइगेनवैल्यू और ईजेनवेक्टर हैं, और मान लीजिए कि इसकी बहुलता n - d है। फिर मैट्रिक्स {{nobreak|1=ρ''I'' + ''A''}} रैंक d का सकारात्मक अर्ध-निश्चित है और इस प्रकार यूक्लिडियन डी-स्पेस में n वैक्टर के आंतरिक उत्पादों के [[ग्राम मैट्रिक्स]] के रूप में प्रदर्शित किया जा सकता है। जैसा कि इन वैक्टरों में एक ही मानदंड (गणित) है (अर्थात्, <math>\sqrt{\rho}</math>) और आपसी आंतरिक उत्पाद ±1, उनके द्वारा फैली हुई n रेखाओं की कोई भी जोड़ी समान कोण φ में मिलती है जहाँ cos φ = 1/ρ। इसके विपरीत, एक यूक्लिडियन अंतरिक्ष में गैर-ऑर्थोगोनल समकोणीय रेखाओं का कोई भी समुच्चय दो-आलेख़ को जन्म दे सकता है (निर्माण के लिए समान रेखाएं देखें)।<ref>{{harvnb|van Lint|Seidel|1966}}</ref>
उपरोक्त के रूप में संकेतन के साथ, अधिकतम गणनांक n ''n'' ≤ ''d''(ρ<sup>2</sup> - 1)/(ρ<sup>2</sup> - ''d'') को संतुष्ट करती है और सीमित उपलब्ध किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है।
ऊपर के रूप में संकेतन के साथ, अधिकतम कार्डिनैलिटी n संतुष्ट करती है n ≤ d(ρ<sup>2</sup> - 1)/(आर<sup>2</sup> - d) और बाउंड हासिल किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है।


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 41: Line 45:
* [[A. E. Brouwer|Brouwer, A.E.]], Cohen, A.M., and Neumaier, A. (1989),  ''Distance-Regular Graphs.''  Springer-Verlag, Berlin.  Sections 1.5, 3.8, 7.6C.
* [[A. E. Brouwer|Brouwer, A.E.]], Cohen, A.M., and Neumaier, A. (1989),  ''Distance-Regular Graphs.''  Springer-Verlag, Berlin.  Sections 1.5, 3.8, 7.6C.


* {{citation|last1=Cameron|first1=P.J.|last2=van Lint|first2=J.H.|title=Designs, Graphs, Codes and their Links|year=1991|series= London Mathematical Society Student Texts 22|publisher=Cambridge University Press|isbn=978-0-521-42385-4}}
* {{citation|last1=Cameron|first1=P.J.|last2=van Lint|first2=J.H.|title=डिजाइन, रेखांकन, कोड और उनके लिंक|year=1991|series= लंदन मैथमैटिकल सोसाइटी छात्र ग्रंथ 22|publisher=कैम्ब्रिज यूनिवर्सिटी प्रेस|isbn=978-0-521-42385-4}}


* {{citation|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|publisher=Chapman & Hall/ CRC|location=Boca Raton|isbn=1-58488-506-8|edition=2nd|pages=875-882}}
* {{citation|last1=Colbourn|first1=Charles J.|last2=डिनिट्ज़|first2=Jeffrey H.|title=संयोजन डिजाइन की पुस्तिका|year=2007|publisher=चैपमैन एंड हॉल / सीआरसी|location=बोका रैटन|isbn=1-58488-506-8|edition=2nd|pages=875-882}}


* [[Chris Godsil]] and [[Gordon Royle]] (2001),  ''Algebraic Graph Theory.''  Graduate Texts in Mathematics, Vol. 207.  Springer-Verlag, New York.  Chapter 11.
* [[Chris Godsil]] and [[Gordon Royle]] (2001),  ''Algebraic Graph Theory.''  Graduate Texts in Mathematics, Vol. 207.  Springer-Verlag, New York.  Chapter 11.
Line 51: Line 55:
* Taylor, D. E. (1977),  Regular 2-graphs. ''Proceedings of the London Mathematical Society'' (3), vol. 35, pp.&nbsp;257–274.
* Taylor, D. E. (1977),  Regular 2-graphs. ''Proceedings of the London Mathematical Society'' (3), vol. 35, pp.&nbsp;257–274.


* {{citation|last1=van Lint|first1=J. H.|last2=Seidel|first2=J. J.|title=Equilateral point sets in elliptic geometry|series=Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69|journal=Indagationes Mathematicae|volume=28|year=1966|pages=335-348}}
* {{citation|last1=van Lint|first1=J. H.|last2=Seidel|first2=J. J.|title=दीर्घवृत्तीय ज्यामिति में समबाहु बिंदु समुच्चय|series=Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69|journal=इंडैगेशन मैथेमेटिका|volume=28|year=1966|pages=335-348}}
[[Category: सेट के परिवार]] [[Category: बीजगणितीय ग्राफ सिद्धांत]] [[Category: रेखांकन का विस्तार और सामान्यीकरण]]  
[[Category: सेट के परिवार]] [[Category: बीजगणितीय ग्राफ सिद्धांत]] [[Category: रेखांकन का विस्तार और सामान्यीकरण]]  


Revision as of 12:28, 11 May 2023

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

एक दो-आलेख़ एक आलेख़ नहीं है और आलेख़ सिद्धांत में 2-आलेख़ नामक अन्य वस्तुओं के साथ अस्पष्ट नहीं होना चाहिए, जैसे 2-नियमित आलेख़ हैं।

उदाहरण

शीर्ष {1,...,6} के समुच्चय पर अव्यवस्थित त्रिगुण का निम्नलिखित संग्रह दो-आलेख़ है:

123  124  135  146  156  236  245  256  345  346

यह दो-आलेख़ एक नियमित दो-आलेख़ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो त्रिगुण में एक साथ दिखाई देती है।

एक साधारण आलेख G = (V,E) को देखते हुए, शीर्ष समुच्चय V के त्रिगुण का समुच्चय जिसका प्रेरित उपआलेख में किनारों की विषम संख्या होती है, समुच्चय V पर दो-आलेख़ बनाता है। प्रत्येक दो-आलेख़ को इस तरह से दर्शाया जा सकता है।[1] इस उदाहरण को एक साधारण आलेख से दो-आलेख़ के मानक निर्माण के रूप में जाना जाता है।

अधिक सम्मिश्र उदाहरण के रूप में, T को कोर समुच्चय E के साथ एक ट्री होता है। E के सभी त्रिगुणों का समुच्चय जो T के पथ में सम्मिलित नहीं हैं, समुच्चय E पर दो-आलेख़ बनाते हैं।[2]

स्विचन और आलेख

आलेख़ में {X, Y} स्विच करना

एक दो-आलेख़ के स्विचन वर्ग के समान है और हस्ताक्षरित पूर्ण आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है।

एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि शीर्ष के प्रत्येक जोड़े की निकटता को प्रतिलोम देना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार किनारे का समुच्चय बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट हो जाए और एक असन्निकट जोड़ी सन्निकट हो जाए। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के अंतर्गत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग को वैन लिंट & सेडेल (1966) द्वारा प्रस्तावित किया गया था और सीडेल द्वारा विकसित किया गया था; इसे आलेख़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित आलेख़ के स्विचिंग से अलग करने के लिए किया गया है।

ऊपर दिए गए सरल आलेख़ से दो-आलेख़ के मानक निर्माण में, दो आलेख़ समान दो-आलेख़ उत्पन्न करेंगे यदि और केवल यदि वे स्विचिंग के समतुल्य हैं, अर्थात वे एक ही स्विचिंग वर्ग में हैं।

अनुमान कि Γ समुच्चय X पर एक दो-आलेख़ है। X के किसी भी तत्व x के लिए, एक आलेख Γx को शीर्ष समुच्चय X के साथ परिभाषित करें जिसमें कोने y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस आलेख में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण आलेख G दिया गया है, एक नए तत्व x को G के शीर्षों के समुच्चय से जोड़ता है, उसी किनारे के समुच्चय को बनाए रखता है, और उपरोक्त मानक निर्माण को उपयोजित करता है।[3]

एक आलेख़ G के लिए एक ही शीर्ष समुच्चय पर एक हस्ताक्षरित पूर्ण आलेख़ Σ के अनुरुप है, जिसका किनारे G में नकारात्मक हैं और G में नहीं हैं तो सकारात्मक हैं। इसके विपरीत, G Σ का उपआलेख है जिसमें सभी कोने और सभी नकारात्मक किनारे सम्मिलित हैं। G के दो-आलेख़ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के त्रिगुण के समुच्चय के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण आलेख़ समान दो-आलेख़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।

G और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक आलेख H और उसके संबंधित पूर्ण आलेख पर हस्ताक्षर किए जाते हैं।

आसन्नता आव्यूह

दो-आलेख़ का आसन्न आव्यूह संबंधित हस्ताक्षरित पूर्ण आलेख़ का आसन्न आलेख़ है; इस प्रकार यह सममित है, विकर्ण पर शून्य है, और विकर्ण से ±1 प्रविष्टियाँ हैं। यदि G हस्ताक्षरित पूर्ण आलेख़ Σ का पुर्ण आलेख़ है, तो इस आव्यूह को (0, -1, 1)-आसन्नता आव्यूह या G का सीडल आसन्न आव्यूह कहा जाता है। सेडेल आव्यूह में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और असन्निकट शीर्षों के लिए +1 प्रविष्टियाँ हैं।

यदि आलेख़ G और H एक ही स्विचिंग वर्ग में हैं, तो G और H के दो सेडेल आसन्न आव्यूह के अभिलक्षणिक मानों के बहुसमुच्चय अनुरूप हैं क्योंकि मेट्रिसेस समान हैं।[4]

एक समुच्चय V पर दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न आव्यूह में केवल दो अलग-अलग अभिलक्षणिक मान और ईजेनवेक्टर ρ1 > 0 > ρ2 कहते हैं, जहां ρ1ρ2 = 1 - |V| हैं।[5]

समकोण रेखाएँ

Main article: समकोण रेखाएँ

प्रत्येक दो-आलेख़ कुछ आयामी यूक्लिडियन समष्टि में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। n शीर्षों पर दो आलेख से निर्मित रेखाओं का समुच्चय इस प्रकार प्राप्त होता है। अनुमान -ρ दो-आलेख़ के सेडेल आसन्न आव्यूह, A के सबसे लघुतम अभिलक्षणिक मान है और अपेक्षित इसकी बहुलता n - d है। तब आव्यूह ρI + A श्रेणी d का सकारात्मक अर्ध-निश्चित है और इस प्रकार यूक्लिडियन d-समष्टि में n सदिश के आंतरिक उत्पादों के ग्राम आव्यूह के रूप में प्रदर्शित किया जा सकता है। जैसा कि इन सदिशों के समान प्रतिमान (अर्थात्, ) और आपसी आंतरिक उत्पाद ±1 हैं, उनके द्वारा विस्तरित n रेखाओं की कोई भी जोड़ी समान कोण φ में मिलती है जहाँ cos φ = 1/ρ है। इसके विपरीत, एक यूक्लिडियन समष्टि में गैर-लंबकोणिक समकोणीय रेखाओं का कोई भी समुच्चय दो-आलेख़ को वृद्धि दे सकता है (निर्माण के लिए समान रेखाएं देखें)।[6]

उपरोक्त के रूप में संकेतन के साथ, अधिकतम गणनांक n n ≤ d(ρ2 - 1)/(ρ2 - d) को संतुष्ट करती है और सीमित उपलब्ध किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है।

टिप्पणियाँ

  1. ↑ Colburn & Dinitz 2007, p. 876, Remark 13.2
  2. ↑ Cameron, P.J. (1994), "Two-graphs and trees", Discrete Mathematics, 127: 63–74 cited in Colburn & Dinitz 2007, p. 876, Construction 13.12
  3. ↑ Cameron & van Lint 1991, pp. 58-59
  4. ↑ Cameron & van Lint 1991, p. 61
  5. ↑ Colburn & Dinitz 2007, p. 878 #13.24
  6. ↑ van Lint & Seidel 1966

संदर्भ

  • Brouwer, A.E., Cohen, A.M., and Neumaier, A. (1989), Distance-Regular Graphs. Springer-Verlag, Berlin. Sections 1.5, 3.8, 7.6C.
  • Cameron, P.J.; van Lint, J.H. (1991), डिजाइन, रेखांकन, कोड और उनके लिंक, लंदन मैथमैटिकल सोसाइटी छात्र ग्रंथ 22, कैम्ब्रिज यूनिवर्सिटी प्रेस, ISBN 978-0-521-42385-4
  • Colbourn, Charles J.; डिनिट्ज़, Jeffrey H. (2007), संयोजन डिजाइन की पुस्तिका (2nd ed.), बोका रैटन: चैपमैन एंड हॉल / सीआरसी, pp. 875–882, ISBN 1-58488-506-8
  • Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York. Chapter 11.
  • Seidel, J. J. (1976), A survey of two-graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rome, 1973), Vol. I, pp. 481–511. Atti dei Convegni Lincei, No. 17. Accademia Nazionale dei Lincei, Rome.
  • Taylor, D. E. (1977), Regular 2-graphs. Proceedings of the London Mathematical Society (3), vol. 35, pp. 257–274.
  • van Lint, J. H.; Seidel, J. J. (1966), "दीर्घवृत्तीय ज्यामिति में समबाहु बिंदु समुच्चय", इंडैगेशन मैथेमेटिका, Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28: 335–348
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=दो-ग्राफ&oldid=159953’