दो-ग्राफ: Difference between revisions
(Created page with "गणित में, एक दो-ग्राफ एक परिमित शीर्ष समुच्चय ''X'' से चुने गए (अक्रमित)...") |
(TEXT) |
||
| Line 1: | Line 1: | ||
गणित में, एक दो- | गणित में, एक दो-आलेख़ एक परिमित शीर्ष समुच्चय ''X'' से चयन किए गए (अक्रमित) त्रिगुणों का एक समूह है, जैसे कि ''X'' से प्रत्येक (अक्रमित) चार गुना में दो-आलेख के त्रिगुणों की एक समान संख्या होती है। एक नियमित दो-आलेख़ में यह गुण होता है कि प्रत्येक जोड़ी के शीर्ष दो-आलेख़ के समान संख्या में त्रिगुण होते हैं। समकोणीय रेखाओं के साथ उनके संबंध के कारण दो-आलेख़ों का अध्ययन किया गया है और नियमित दो-आलेख़ों के लिए, दृढ़ता से [[नियमित ग्राफ|नियमित रेखांकन]] और [[परिमित समूह]] भी हैं क्योंकि कई नियमित दो-आलेख़ों में रोचक स्वसमाकृतिकता समूह होते हैं। | ||
एक दो- | एक दो-आलेख़ एक आलेख़ नहीं है और आलेख़ सिद्धांत में 2-आलेख़ नामक अन्य वस्तुओं के साथ अस्पष्ट नहीं होना चाहिए, जैसे 2-नियमित आलेख़ हैं। | ||
== उदाहरण == | == उदाहरण == | ||
शीर्ष {1,...,6} के समुच्चय पर अव्यवस्थित त्रिगुण का निम्नलिखित संग्रह दो-आलेख़ है: | |||
:123 124 135 146 156 236 245 256 345 346 | :123 124 135 146 156 236 245 256 345 346 | ||
यह दो- | यह दो-आलेख़ एक नियमित दो-आलेख़ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो त्रिगुण में एक साथ दिखाई देती है। | ||
एक साधारण | एक साधारण आलेख ''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> | ||
== स्विचन और आलेख == | |||
[[file:Xyswitch.svg|thumb|आलेख़ में {X, Y} स्विच करना]]एक दो-आलेख़ के स्विचन वर्ग के समान है और [[हस्ताक्षरित ग्राफ|हस्ताक्षरित पूर्ण]] आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है। | |||
एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि प्रत्येक जोड़ी के शीर्ष की आसन्नता को प्रतिलोम देना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार एज समुच्चय को बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट और एक असन्निकट जोड़ी बन जाए समीप हो जाता है। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के तहत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग द्वारा पेश किया गया था {{harvtxt|van Lint|Seidel|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> एक आलेख़ जी के लिए एक ही त्रिभुज समुच्चय पर एक हस्ताक्षरित पूर्ण आलेख़ Σ से मेल खाता है, जिसका किनारों को जी में नहीं तो सकारात्मक और सकारात्मक पर हस्ताक्षर किए गए हैं। इसके विपरीत, जी Σ का सबआलेख है जिसमें सभी कोने और सभी नकारात्मक किनारे सम्मिलित हैं। जी के दो-आलेख़ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के त्रिगुण के समुच्चय के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण आलेख़ समान दो-आलेख़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं। | ||
जी और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक आलेख एच और उसके संबंधित पूर्ण आलेख पर हस्ताक्षर किए जाते हैं। | |||
जी और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक | |||
== निकटता मैट्रिक्स == | == निकटता मैट्रिक्स == | ||
दो- | दो-आलेख़ का आसन्न मैट्रिक्स संबंधित हस्ताक्षरित पूर्ण आलेख़ का हस्ताक्षरित आलेख़ है; इस प्रकार यह [[सममित मैट्रिक्स]] है, विकर्ण पर शून्य है, और विकर्ण से प्रविष्टियाँ ±1 हैं। यदि ''G'' हस्ताक्षरित पूर्ण आलेख़ Σ के संगत आलेख़ है, तो इस मैट्रिक्स को (0, -1, 1)-आसन्नता मैट्रिक्स या ''G'' का सीडल आसन्न मैट्रिक्स कहा जाता है। सेडेल मैट्रिक्स में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और गैर-निकटवर्ती शीर्षों के लिए +1 प्रविष्टियाँ हैं। | ||
यदि आलेख़ ''G'' और ''H'' एक ही स्विचिंग वर्ग में हैं, तो ''G'' और ''H'' के दो सेडेल आसन्न मैट्रिक्स के eigenvalues के मल्टीसमुच्चय मेल खाते हैं क्योंकि मेट्रिसेस समान हैं।<ref>{{harvnb|Cameron|van Lint|1991|loc=p. 61}}</ref> | |||
एक समुच्चय वी पर एक दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न मैट्रिक्स में केवल दो अलग-अलग ईजेनवैल्यू और ईजेनवेक्टर ρ हैं<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> | |||
== समकोण रेखाएँ == | == समकोण रेखाएँ == | ||
{{main|Equiangular lines}} | {{main|Equiangular lines}} | ||
प्रत्येक दो- | प्रत्येक दो-आलेख़ कुछ आयामी [[यूक्लिडियन अंतरिक्ष]] में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। 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) और बाउंड हासिल किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है। | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
{{reflist}} | {{reflist}} | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 22:50, 10 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]
स्विचन और आलेख
एक दो-आलेख़ के स्विचन वर्ग के समान है और हस्ताक्षरित पूर्ण आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है।
एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि प्रत्येक जोड़ी के शीर्ष की आसन्नता को प्रतिलोम देना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार एज समुच्चय को बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट और एक असन्निकट जोड़ी बन जाए समीप हो जाता है। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के तहत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग द्वारा पेश किया गया था van Lint & Seidel (1966) और सीडेल द्वारा विकसित; इसे आलेख़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित आलेख़ के स्विचिंग से अलग करने के लिए।
ऊपर दिए गए सरल आलेख़ से दो-आलेख़ के मानक निर्माण में, दो आलेख़ समान दो-आलेख़ उत्पन्न करेंगे यदि और केवल यदि वे स्विचिंग के समतुल्य हैं, अर्थात वे एक ही स्विचिंग वर्ग में हैं।
मान लीजिए कि 'X' समुच्चय पर Γ एक दो-आलेख़ है। X के किसी भी तत्व x के लिए, एक आलेख Γ परिभाषित करेंx त्रिभुज समुच्चय X के साथ शीर्ष y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस आलेख में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण आलेख जी दिया गया है, एक नए तत्व एक्स को जी के शीर्षों के समुच्चय से जोड़ता है, उसी किनारे के समुच्चय को बनाए रखता है, और उपरोक्त मानक निर्माण को लागू करता है।[3] एक आलेख़ जी के लिए एक ही त्रिभुज समुच्चय पर एक हस्ताक्षरित पूर्ण आलेख़ Σ से मेल खाता है, जिसका किनारों को जी में नहीं तो सकारात्मक और सकारात्मक पर हस्ताक्षर किए गए हैं। इसके विपरीत, जी Σ का सबआलेख है जिसमें सभी कोने और सभी नकारात्मक किनारे सम्मिलित हैं। जी के दो-आलेख़ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के त्रिगुण के समुच्चय के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण आलेख़ समान दो-आलेख़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।
जी और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक आलेख एच और उसके संबंधित पूर्ण आलेख पर हस्ताक्षर किए जाते हैं।
निकटता मैट्रिक्स
दो-आलेख़ का आसन्न मैट्रिक्स संबंधित हस्ताक्षरित पूर्ण आलेख़ का हस्ताक्षरित आलेख़ है; इस प्रकार यह सममित मैट्रिक्स है, विकर्ण पर शून्य है, और विकर्ण से प्रविष्टियाँ ±1 हैं। यदि G हस्ताक्षरित पूर्ण आलेख़ Σ के संगत आलेख़ है, तो इस मैट्रिक्स को (0, -1, 1)-आसन्नता मैट्रिक्स या G का सीडल आसन्न मैट्रिक्स कहा जाता है। सेडेल मैट्रिक्स में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और गैर-निकटवर्ती शीर्षों के लिए +1 प्रविष्टियाँ हैं।
यदि आलेख़ G और H एक ही स्विचिंग वर्ग में हैं, तो G और H के दो सेडेल आसन्न मैट्रिक्स के eigenvalues के मल्टीसमुच्चय मेल खाते हैं क्योंकि मेट्रिसेस समान हैं।[4] एक समुच्चय वी पर एक दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न मैट्रिक्स में केवल दो अलग-अलग ईजेनवैल्यू और ईजेनवेक्टर ρ हैं1 > 0 > प2 कहते हैं, जहां ρ1ρ2 = 1 - |वी|।[5]
समकोण रेखाएँ
प्रत्येक दो-आलेख़ कुछ आयामी यूक्लिडियन अंतरिक्ष में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। n शीर्षों पर दो आलेख से निर्मित रेखाओं का समुच्चय इस प्रकार प्राप्त होता है। चलो -ρ दो-आलेख़ के सेडेल आसन्न मैट्रिक्स, ए के सबसे छोटे आइगेनवैल्यू और ईजेनवेक्टर हैं, और मान लीजिए कि इसकी बहुलता n - d है। फिर मैट्रिक्स ρI + A रैंक d का सकारात्मक अर्ध-निश्चित है और इस प्रकार यूक्लिडियन डी-स्पेस में n वैक्टर के आंतरिक उत्पादों के ग्राम मैट्रिक्स के रूप में प्रदर्शित किया जा सकता है। जैसा कि इन वैक्टरों में एक ही मानदंड (गणित) है (अर्थात्, ) और आपसी आंतरिक उत्पाद ±1, उनके द्वारा फैली हुई n रेखाओं की कोई भी जोड़ी समान कोण φ में मिलती है जहाँ cos φ = 1/ρ। इसके विपरीत, एक यूक्लिडियन अंतरिक्ष में गैर-ऑर्थोगोनल समकोणीय रेखाओं का कोई भी समुच्चय दो-आलेख़ को जन्म दे सकता है (निर्माण के लिए समान रेखाएं देखें)।[6] ऊपर के रूप में संकेतन के साथ, अधिकतम कार्डिनैलिटी n संतुष्ट करती है n ≤ d(ρ2 - 1)/(आर2 - d) और बाउंड हासिल किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है।
टिप्पणियाँ
- ↑ Colburn & Dinitz 2007, p. 876, Remark 13.2
- ↑ Cameron, P.J. (1994), "Two-graphs and trees", Discrete Mathematics, 127: 63–74 cited in Colburn & Dinitz 2007, p. 876, Construction 13.12
- ↑ Cameron & van Lint 1991, pp. 58-59
- ↑ Cameron & van Lint 1991, p. 61
- ↑ Colburn & Dinitz 2007, p. 878 #13.24
- ↑ 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), Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, ISBN 978-0-521-42385-4
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, 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), "Equilateral point sets in elliptic geometry", Indagationes Mathematicae, Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28: 335–348
