दो-ग्राफ

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

एक दो-ग्राफ़ एक ग्राफ़ नहीं है और ग्राफ़ सिद्धांत में 2-ग्राफ़ नामक अन्य वस्तुओं के साथ भ्रमित नहीं होना चाहिए, जैसे कि नियमित ग्राफ़ | 2-नियमित ग्राफ़।

उदाहरण

वर्टिकल {1,...,6} के सेट पर अनियंत्रित ट्रिपल का निम्नलिखित संग्रह दो-ग्राफ है:

123  124  135  146  156  236  245  256  345  346

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

एक साधारण ग्राफ जी = (वी, ई) को देखते हुए, वर्टेक्स सेट वी के ट्रिपल का सेट जिसका प्रेरित सबग्राफ में किनारों की विषम संख्या है, सेट वी पर एक दो-ग्राफ बनाता है। प्रत्येक दो-ग्राफ को इस तरह से दर्शाया जा सकता है . इस उदाहरण को एक साधारण ग्राफ से दो-ग्राफ के मानक निर्माण के रूप में जाना जाता है।

अधिक जटिल उदाहरण के रूप में, टी को एज सेट ई के साथ एक पेड़ होने दें। ई के सभी त्रिभुजों का सेट जो टी के पथ में शामिल नहीं हैं, सेट ई पर दो-ग्राफ बनाते हैं।

स्विचिंग और ग्राफ

ग्राफ़ में {X, Y} स्विच करना

एक दो-ग्राफ़ ग्राफ़ के स्विचिंग क्लास के बराबर है और हस्ताक्षरित ग्राफ़ के स्विचिंग क्लास (हस्ताक्षरित) के बराबर है।

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

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

मान लीजिए कि 'X' सेट पर Γ एक दो-ग्राफ है। X के किसी भी तत्व x के लिए, एक ग्राफ Γ परिभाषित करें_x वर्टेक्स सेट X के साथ वर्टिकल y और z आसन्न हैं यदि और केवल यदि {x, y, z} Γ में है। इस ग्राफ में, x एक विलगित शीर्ष होगा। यह निर्माण प्रतिवर्ती है; एक साधारण ग्राफ जी दिया गया है, एक नए तत्व एक्स को जी के शीर्षों के सेट से जोड़ता है, उसी किनारे के सेट को बनाए रखता है, और उपरोक्त मानक निर्माण को लागू करता है। एक ग्राफ़ जी के लिए एक ही वर्टेक्स सेट पर एक हस्ताक्षरित पूर्ण ग्राफ़ Σ से मेल खाता है, जिसका किनारों को जी में नहीं तो सकारात्मक और सकारात्मक पर हस्ताक्षर किए गए हैं। इसके विपरीत, जी Σ का सबग्राफ है जिसमें सभी कोने और सभी नकारात्मक किनारे शामिल हैं। जी के दो-ग्राफ को Σ में नकारात्मक त्रिकोण (ऋणात्मक किनारों की विषम संख्या वाला त्रिकोण) का समर्थन करने वाले शीर्षों के ट्रिपल के सेट के रूप में भी परिभाषित किया जा सकता है। दो हस्ताक्षरित पूर्ण ग्राफ़ समान दो-ग्राफ़ उत्पन्न करते हैं यदि और केवल यदि वे स्विचिंग के समतुल्य हैं।

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

निकटता मैट्रिक्स

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

यदि ग्राफ़ G और H एक ही स्विचिंग क्लास में हैं, तो G और H के दो सेडेल आसन्न मैट्रिक्स के eigenvalues ​​​​के मल्टीसेट मेल खाते हैं क्योंकि मेट्रिसेस समान हैं। एक सेट वी पर एक दो-ग्राफ नियमित है अगर और केवल अगर इसके आसन्न मैट्रिक्स में केवल दो अलग-अलग ईजेनवैल्यू और ईजेनवेक्टर ρ हैं₁ > 0 > प₂ कहते हैं, जहां ρ₁ρ₂ = 1 - |वी|।

समकोण रेखाएँ

Main article: Equiangular lines

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

संदर्भ

• 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