बीजगणितीय ग्राफ सिद्धांत

बीजगणितीय ग्राफ सिद्धांत गणित की एक शाखा है जिसमें ग्राफ के साथ समस्याओं पर बीजगणितीय विधियों को लागू किया जाता है। यह ज्यामितीय, संयोजक, या एल्गोरिथम दृष्टिकोणों के विपरीत है। बीजीय ग्राफ सिद्धांत की तीन मुख्य शाखाएँ हैं, जिसमें रैखिक बीजगणित का उपयोग, समूह सिद्धांत का उपयोग और ग्राफ अपरिवर्तनीय का अध्ययन सम्मिलित है।

अत्यधिक सममित ग्राफ, पीटरसन ग्राफ, वर्टेक्स-सकर्मक, सममित, दूरी-संक्रमणीय और दूरी-नियमित है। इसका एक व्यास 2 है। इसके ऑटोमोर्फिज़्म समूह में 120 अवयव हैं और वास्तव में सममित समूह $S_{5}$ है।

बीजगणितीय ग्राफ सिद्धांत की शाखाएँ

रैखिक बीजगणित का प्रयोग

बीजीय ग्राफ सिद्धांत की पहली शाखा में रेखीय बीजगणित के संबंध में ग्राफ का अध्ययन सम्मिलित है। यह विशेष रूप से आसन्न मैट्रिक्स के स्पेक्ट्रम का अध्ययन करता है, या ग्राफ के लाप्लासियन मैट्रिक्स (बीजीय ग्राफ सिद्धांत के इस भाग को वर्णक्रमीय ग्राफ सिद्धांत भी कहा जाता है)। पीटरसन ग्राफ के लिए, उदाहरण के लिए, आसन्न मैट्रिक्स का स्पेक्ट्रम (-2, -2, -2, -2, 1, 1, 1, 1, 1, 3) है। कई प्रमेय स्पेक्ट्रम के गुणों को अन्य ग्राफ गुणों से जोड़ते हैं। सरल उदाहरण के रूप में, व्यास D के साथ एक जुड़े हुए ग्राफ के स्पेक्ट्रम में कम से कम D+1 भिन्न मान होंगे। नेटवर्क की तुल्यकालन क्षमता का विश्लेषण करने के लिए ग्राफ स्पेक्ट्रा के पक्ष का उपयोग किया गया है।

समूह सिद्धांत का प्रयोग

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph|t-transitive, t ≥ 2]]		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

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

वैकल्पिक समूह A4 के लिए केली ग्राफ, तीन आयामों में छोटा चतुष्फलक बनाता है। सभी केली ग्राफ शीर्ष-सकर्मक हैं, लेकिन कुछ शीर्ष-संक्रमणीय ग्राफ (जैसे पीटरसन ग्राफ) केली ग्राफ नहीं हैं।

3 रंगों के साथ पीटरसन ग्राफ का उचित शीर्ष रंग, न्यूनतम संभव संख्या। रंगीन बहुपद के अनुसार, 120 ऐसे रंग हैं जिनमें 3 रंग हैं।

बीजगणितीय ग्राफ़ सिद्धांत की यह दूसरी शाखा पहले से संबंधित है क्योंकि ग्राफ़ के समरूपता गुण इसके स्पेक्ट्रम में दिखाई देते हैं। विशेष रूप से, अत्यधिक सममित ग्राफ के स्पेक्ट्रम, जैसे कि पीटरसन ग्राफ, के कुछ अलग मूल्य हैं (पीटरसन ग्राफ में 3 है, जो न्यूनतम संभव है, इसके व्यास को देखते हुए)। विशेष रूप से इसके अलघुकरणीय वर्णों से, केली ग्राफ के लिए, स्पेक्ट्रम को सीधे समूह की संरचना से संबंधित किया जा सकता है,

ग्राफ अपरिवर्तनशीलताओं का अध्ययन

अंत में, बीजगणितीय ग्राफ सिद्धांत की तीसरी शाखा ग्राफ के अपरिवर्तनशीलताओं के बीजगणितीय गुणों से संबंधित है, विशेष रूप से रंगीन बहुपद, टुटे बहुपद और वृक्षसंधि अपरिवर्तनीय से संबंधित है। ग्राफ के रंगीन बहुपद, उदाहरण के लिए, इसके उचित शीर्ष रंगों की संख्या की गणना करता है। पीटरसन ग्राफ के लिए, यह बहुपद है $t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$. विशेष रूप से, इसका अर्थ है कि पीटरसन ग्राफ को एक या दो रंगों से ठीक से रंगा नहीं जा सकता है, लेकिन 120 अलग-अलग विधियों से 3 रंगों से रंगा जा सकता है। बीजगणितीय ग्राफ सिद्धांत के इस क्षेत्र में काफी कार्य चार रंगों के प्रमेय को सिद्ध करने के प्रयासों से प्रेरित था। हालाँकि, अभी भी कई विवृत समस्याएँ हैं, जैसे कि ग्राफ़ को चित्रित करना जिसमें समान रंगीन बहुपद हैं, और यह निर्धारित करना कि कौन से बहुपद वर्णक्रमीय हैं।

यह भी देखें

• वर्णक्रमीय रेखांकन सिद्धांत
• बीजगणितीय कॉम्बिनेटरिक्स
• बीजीय संयोजकता
• डल्मेज-मेंडेलसोहन अपघटन
• ग्राफ़ गुण
• निकटता मैट्रिक्स

संदर्भ

• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, ISBN 0-387-95220-9, Zbl 0968.05002.

बाहरी संबंध

• Media related to बीजगणितीय ग्राफ सिद्धांत at Wikimedia Commons