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

Latest revision as of 17:18, 17 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 पर दो-आलेख़ नियमित है अगर और केवल अगर इसके आसन्न आव्यूह में केवल दो अलग-अलग अभिलक्षणिक मान ρ₁ > 0 > ρ₂ कहते हैं, जहां ρ₁ρ₂ = 1 - |V| हैं।^[5]

समकोण रेखाएँ

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

उपरोक्त के रूप में संकेतन के साथ, अधिकतम गणनांक n n ≤ d(ρ² - 1)/(ρ² - 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), डिजाइन, रेखांकन, कोड और उनके लिंक, लंदन मैथमैटिकल सोसाइटी छात्र ग्रंथ 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

[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

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
-गणित में, एक दो-ग्राफ एक परिमित शीर्ष समुच्चय ''X'' से चुने गए (अक्रमित) त्रिगुणों का एक समूह है, जैसे कि ''X'' से प्रत्येक (अक्रमित) चौगुनी में दो के त्रिगुणों की एक समान संख्या होती है- ग्राफ। एक नियमित दो-ग्राफ़ में यह गुण होता है कि प्रत्येक जोड़ी के शीर्ष दो-ग्राफ़ के समान संख्या में समान संख्या में होते हैं। समकोणीय रेखाओं के साथ उनके संबंध के कारण दो-ग्राफ़ों का अध्ययन किया गया है और नियमित दो-ग्राफ़ों के लिए, दृढ़ता से [[नियमित ग्राफ]]़ और [[परिमित समूह]] भी हैं क्योंकि कई नियमित दो-ग्राफ़ों में दिलचस्प ऑटोमोर्फिज़्म समूह होते हैं।
+गणित में, दो-आलेख़ एक परिमित शीर्ष समुच्चय ''X'' से चयन किए गए (अक्रमित) त्रिगुणों का एक समूह है, जैसे कि ''X'' से प्रत्येक (अक्रमित) चौगुना में दो-आलेख के त्रिगुणों की एक समान संख्या होती है। एक नियमित दो-आलेख़ में यह गुण होते है कि प्रत्येक जोड़ी के शीर्ष दो-आलेख़ के समान संख्या में त्रिगुण होते हैं। समकोणीय रेखाओं के साथ उनके संबंध के कारण दो-आलेख़ों का अध्ययन किया गया है और नियमित दो-आलेख़ों के लिए, दृढ़ता से [[नियमित ग्राफ|नियमित रेखांकन]] और [[परिमित समूह]] भी हैं क्योंकि कई नियमित दो-आलेख़ों में रोचक स्वसमाकृतिकता समूह होते हैं।
-एक दो-ग्राफ़ एक ग्राफ़ नहीं है और ग्राफ़ सिद्धांत में 2-ग्राफ़ नामक अन्य वस्तुओं के साथ भ्रमित नहीं होना चाहिए, जैसे कि नियमित ग्राफ़ | 2-नियमित ग्राफ़।
+दो-आलेख़ एक आलेख़ नहीं है और आलेख़ सिद्धांत में 2-आलेख़ नामक अन्य वस्तुओं के साथ अस्पष्ट नहीं होना चाहिए, जैसे 2-नियमित आलेख़ हैं।
 == उदाहरण ==
-वर्टिकल {1,...,6} के सेट पर अनियंत्रित ट्रिपल का निम्नलिखित संग्रह दो-ग्राफ है:
+शीर्ष {1,...,6} के समुच्चय पर अव्यवस्थित त्रिगुण का निम्नलिखित संग्रह दो-आलेख़ है:
 :123  124  135  146  156  236  245  256  345  346
-यह दो-ग्राफ एक नियमित दो-ग्राफ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो ट्रिपल में एक साथ दिखाई देती है।
+यह दो-आलेख़ एक नियमित दो-आलेख़ है क्योंकि अलग-अलग शीर्षों की प्रत्येक जोड़ी बिल्कुल दो त्रिगुण में एक साथ दिखाई देती है।
-एक साधारण ग्राफ जी = (वी, ई) को देखते हुए, वर्टेक्स सेट वी के ट्रिपल का सेट जिसका प्रेरित सबग्राफ में किनारों की विषम संख्या है, सेट वी पर एक दो-ग्राफ बनाता है। प्रत्येक दो-ग्राफ को इस तरह से दर्शाया जा सकता है .<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> इस उदाहरण को एक साधारण आलेख से दो-आलेख़ के मानक निर्माण के रूप में जाना जाता है।
-अधिक जटिल उदाहरण के रूप में, टी को एज सेट ई के साथ एक पेड़ होने दें। ई के सभी त्रिभुजों का सेट जो टी के पथ में शामिल नहीं हैं, सेट ई पर दो-ग्राफ बनाते हैं।<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>
+== स्विचन और आलेख ==
+[[file:Xyswitch.svg|thumb|आलेख़ में {X, Y} स्विच करना]]एक दो-आलेख़ के स्विचन वर्ग के समान है और [[हस्ताक्षरित ग्राफ|हस्ताक्षरित पूर्ण]] आलेख़ के (हस्ताक्षरित) स्विचिंग वर्ग के समान है।
+एक (सरल) आलेख़ में शीर्ष के एक समुच्चय को स्विच करने का अर्थ है कि शीर्ष के प्रत्येक जोड़े की आसन्नताओं को प्रतिलोम करना, एक समुच्चय में और दूसरा समुच्चय में नहीं: इस प्रकार किनारे का समुच्चय बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट हो जाए और एक असन्निकट जोड़ी सन्निकट हो जाए। वे किनारे जिनके अंत बिंदु दोनों समुच्चय में हैं, या दोनों समुच्चय में नहीं हैं, बदले नहीं गए हैं। आलेख़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के अंतर्गत आलेख़ के समतुल्य वर्ग को स्विचिंग वर्ग कहा जाता है। स्विचिंग को {{harvtxt|वैन लिंट|सेडेल|1966}} द्वारा प्रस्तावित किया गया था और सीडेल द्वारा विकसित किया गया था; इसे आलेख़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित आलेख़ के स्विचिंग से अलग करने के लिए किया गया है।
-== स्विचिंग और ग्राफ ==
+ऊपर दिए गए सरल आलेख़ से दो-आलेख़ के मानक निर्माण में, दो आलेख़ समान दो-आलेख़ उत्पन्न करेंगे यदि और केवल यदि वे स्विचिंग के समतुल्य हैं, अर्थात वे एक ही स्विचिंग वर्ग में हैं।
-[[file:Xyswitch.svg|thumb|ग्राफ़ में {X, Y} स्विच करना]]एक दो-ग्राफ़ ग्राफ़ के स्विचिंग क्लास के बराबर है और [[हस्ताक्षरित ग्राफ]]़ के स्विचिंग क्लास (हस्ताक्षरित) के बराबर है।
-एक (सरल) ग्राफ़ में वर्टिकल के एक सेट को स्विच करने का मतलब है कि प्रत्येक जोड़ी के वर्टिकल की आसन्नता को उलट देना, एक सेट में और दूसरा सेट में नहीं: इस प्रकार एज सेट को बदल दिया जाता है ताकि एक आसन्न जोड़ी असन्निकट और एक असन्निकट जोड़ी बन जाए समीप हो जाता है। वे किनारे जिनके अंत बिंदु दोनों सेट में हैं, या दोनों सेट में नहीं हैं, बदले नहीं गए हैं। ग्राफ़ समतुल्य स्विच कर रहे हैं यदि स्विच करके दूसरे से प्राप्त किया जा सकता है। स्विचिंग के तहत ग्राफ़ के समतुल्य वर्ग को स्विचिंग क्लास कहा जाता है। स्विचिंग द्वारा पेश किया गया था {{harvtxt|van Lint|Seidel|1966}} और सीडेल द्वारा विकसित; इसे ग्राफ़ स्विचिंग या सेडेल स्विचिंग कहा गया है, आंशिक रूप से इसे हस्ताक्षरित ग्राफ़ के स्विचिंग से अलग करने के लिए।
+अनुमान कि Γ समुच्चय 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'' के दो-आलेख़ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के त्रिगुण के समुच्चय के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण आलेख़ समान दो-आलेख़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।
-मान लीजिए कि 'X' सेट पर Γ एक दो-ग्राफ है। ''X'' के किसी भी तत्व ''x'' के लिए, एक ग्राफ Γ परिभाषित करें<sub>''x''</sub> वर्टेक्स सेट X के साथ वर्टिकल y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस ग्राफ में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण ग्राफ जी दिया गया है, एक नए तत्व एक्स को जी के शीर्षों के सेट से जोड़ता है, उसी किनारे के सेट को बनाए रखता है, और उपरोक्त मानक निर्माण को लागू करता है।<ref>{{harvnb|Cameron|van Lint|1991|loc=pp. 58-59}}</ref> एक ग्राफ़ जी के लिए एक ही वर्टेक्स सेट पर एक हस्ताक्षरित पूर्ण ग्राफ़ Σ से मेल खाता है, जिसका किनारों को जी में नहीं तो सकारात्मक और सकारात्मक पर हस्ताक्षर किए गए हैं। इसके विपरीत, जी Σ का सबग्राफ है जिसमें सभी कोने और सभी नकारात्मक किनारे शामिल हैं। जी के दो-ग्राफ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के ट्रिपल के सेट के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण ग्राफ़ समान दो-ग्राफ़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।
+''G'' और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक आलेख ''H'' और उसके संबंधित पूर्ण आलेख पर हस्ताक्षर किए जाते हैं।
-जी और Σ का स्विचिंग संबंधित हैं: दोनों में एक ही कोने को बदलने से एक ग्राफ एच और उसके संबंधित पूर्ण ग्राफ पर हस्ताक्षर किए जाते हैं।
+== आसन्नता आव्यूह ==
-== निकटता मैट्रिक्स ==
+दो-आलेख़ का आसन्न आव्यूह संबंधित हस्ताक्षरित पूर्ण आलेख़ का आसन्न आलेख़ है; इस प्रकार यह [[सममित मैट्रिक्स|सममित]] है, विकर्ण पर शून्य है, और विकर्ण से ±1 प्रविष्टियाँ हैं। यदि ''G'' हस्ताक्षरित पूर्ण आलेख़ Σ का पुर्ण आलेख़ है, तो इस आव्यूह को (0, -1, 1)-आसन्नता आव्यूह या ''G'' का सीडल आसन्न आव्यूह कहा जाता है। सेडेल आव्यूह में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और असन्निकट शीर्षों के लिए +1 प्रविष्टियाँ हैं।
-दो-ग्राफ़ का आसन्न मैट्रिक्स संबंधित हस्ताक्षरित पूर्ण ग्राफ़ का हस्ताक्षरित ग्राफ़ है; इस प्रकार यह [[सममित मैट्रिक्स]] है, विकर्ण पर शून्य है, और विकर्ण से प्रविष्टियाँ ±1 हैं। यदि ''G'' हस्ताक्षरित पूर्ण ग्राफ़ Σ के संगत ग्राफ़ है, तो इस मैट्रिक्स को (0, -1, 1)-आसन्नता मैट्रिक्स या ''G'' का सीडल आसन्न मैट्रिक्स कहा जाता है। सेडेल मैट्रिक्स में मुख्य विकर्ण पर शून्य प्रविष्टियाँ हैं, आसन्न शीर्षों के लिए -1 प्रविष्टियाँ और गैर-निकटवर्ती शीर्षों के लिए +1 प्रविष्टियाँ हैं।
+यदि आलेख़ ''G'' और ''H'' एक ही स्विचिंग वर्ग में हैं, तो ''G'' और ''H'' के दो सेडेल आसन्न आव्यूह के अभिलक्षणिक मानों के बहुसमुच्चय अनुरूप हैं क्योंकि मेट्रिसेस समान हैं।<ref>{{harvnb|Cameron|van Lint|1991|loc=p. 61}}</ref>
-यदि ग्राफ़ ''G'' और ''H'' एक ही स्विचिंग क्लास में हैं, तो ''G'' और ''H'' के दो सेडेल आसन्न मैट्रिक्स के eigenvalues के मल्टीसेट मेल खाते हैं क्योंकि मेट्रिसेस समान हैं।<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>
-एक सेट वी पर एक दो-ग्राफ नियमित है अगर और केवल अगर इसके आसन्न मैट्रिक्स में केवल दो अलग-अलग ईजेनवैल्यू और ईजेनवेक्टर ρ हैं<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|समकोण रेखाएँ}}
+प्रत्येक दो-आलेख़ कुछ आयामी [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन समष्टि]] में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। 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''(ρ<sup>2</sup> - 1)/(ρ<sup>2</sup> - ''d'') को संतुष्ट करती है और सीमित उपलब्ध किया जाता है अगर और केवल अगर दो-आलेख़ नियमित है।
-{{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) और बाउंड हासिल किया जाता है अगर और केवल अगर दो-ग्राफ़ नियमित है।
 ==टिप्पणियाँ==
 {{reflist}}
 ==संदर्भ==
@@ Line 46: / 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.
-* {{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.
@@ Line 56: / Line 55: @@
 * 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: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 08/05/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:बीजगणितीय ग्राफ सिद्धांत]]
+[[Category:रेखांकन का विस्तार और सामान्यीकरण]]
+[[Category:सेट के परिवार]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 17:18, 17 May 2023

Contents

उदाहरण

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

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

समकोण रेखाएँ

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 17:18, 17 May 2023

उदाहरण

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

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

समकोण रेखाएँ

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories