दो-ग्राफ

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

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

उदाहरण

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

123  124  135  146  156  236  245  256  345  346

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समकोण रेखाएँ

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

प्रत्येक दो-आलेख़ कुछ आयामी यूक्लिडियन समष्टि में रेखाओं के एक समुच्चय के समान है, जिनमें से प्रत्येक जोड़ी एक ही कोण में मिलती है। n शीर्षों पर दो आलेख से निर्मित रेखाओं का समुच्चय इस प्रकार प्राप्त होता है। अनुमान -ρ दो-आलेख़ के सेडेल आसन्न आव्यूह, A के सबसे लघुतम अभिलक्षणिक मान है और अपेक्षित इसकी बहुलता n - d है। तब आव्यूह ρI + A श्रेणी d का सकारात्मक अर्ध-निश्चित है और इस प्रकार यूक्लिडियन 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), डिजाइन, रेखांकन, कोड और उनके लिंक, लंदन मैथमैटिकल सोसाइटी छात्र ग्रंथ 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