सममित ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 18: | Line 18: | ||
{{nowrap|{{mvar|t}}-arc}} को {{math|''t'' + 1}} कोने के [[अनुक्रम]] के रूप में परिभाषित किया गया है, जैसे कि अनुक्रम में कोई भी निरंतर दो कोने आसन्न हैं, और किसी भी दोहराए जाने वाले कोने 2 चरणों से अधिक की दूरी है। {{nowrap|{{mvar|t}}-transitive}} ग्राफ ऐसा ग्राफ है जैसे कि ऑटोमोर्फिज्म समूह {{nowrap|{{mvar|t}}-arcs}} पर सकर्मक रूप से कार्य करता है, किंतु {{nowrap|({{math|{{mvar|t}} + 1}})-arcs}} पर नहीं कार्य करता है। चूंकि {{nowrap|1-arcs}} केवल किनारे हैं, डिग्री 3 या उससे अधिक के प्रत्येक सममित ग्राफ को कुछ {{mvar|t}} के लिए {{nowrap|{{mvar|t}}-transitive}} होना चाहिए, और {{mvar|t}} के मान का उपयोग सममित ग्राफ को आगे वर्गीकृत करने के लिए किया जा सकता है। उदाहरण के लिए घन {{nowrap|2-transitive}} है।<ref name="biggs" /> | {{nowrap|{{mvar|t}}-arc}} को {{math|''t'' + 1}} कोने के [[अनुक्रम]] के रूप में परिभाषित किया गया है, जैसे कि अनुक्रम में कोई भी निरंतर दो कोने आसन्न हैं, और किसी भी दोहराए जाने वाले कोने 2 चरणों से अधिक की दूरी है। {{nowrap|{{mvar|t}}-transitive}} ग्राफ ऐसा ग्राफ है जैसे कि ऑटोमोर्फिज्म समूह {{nowrap|{{mvar|t}}-arcs}} पर सकर्मक रूप से कार्य करता है, किंतु {{nowrap|({{math|{{mvar|t}} + 1}})-arcs}} पर नहीं कार्य करता है। चूंकि {{nowrap|1-arcs}} केवल किनारे हैं, डिग्री 3 या उससे अधिक के प्रत्येक सममित ग्राफ को कुछ {{mvar|t}} के लिए {{nowrap|{{mvar|t}}-transitive}} होना चाहिए, और {{mvar|t}} के मान का उपयोग सममित ग्राफ को आगे वर्गीकृत करने के लिए किया जा सकता है। उदाहरण के लिए घन {{nowrap|2-transitive}} है।<ref name="biggs" /> | ||
ध्यान दें कि परंपरागत रूप से | ध्यान दें कि परंपरागत रूप से "सममित ग्राफ" शब्द [[असममित ग्राफ]] शब्द का पूरक नहीं है, क्योंकि उत्तरार्द्ध ऐसे ग्राफ को संदर्भित करता है जिसमें कोई गैर-समरूप समरूपता नहीं है। | ||
== उदाहरण == | == उदाहरण == | ||
किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार [[चक्र ग्राफ]] | किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार [[चक्र ग्राफ]] (2 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: [[ घनक्षेत्र |घनक्षेत्र]], ऑक्टाहेड्रोन, [[विंशतिफलक|आईकोसैहेड्रोन]], [[द्वादशफ़लक]], [[[[octahedron|क्यूबोक्टाहेड्रोन]]]] और [[icosidodecahedron|इकोसिडोडेकेड्रॉन]] हैं। क्यूब का n आयामों तक विस्तार हाइपरक्यूब ग्राफ देता है (2<sup>n</sup> शीर्ष और डिग्री n)। इसी प्रकार ऑक्टाहेड्रॉन से n आयामों का विस्तार [[ क्रॉस-पॉलीटॉप |क्रॉस-पॉलीटोप्स]] के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी [[कॉकटेल पार्टी ग्राफ]] के रूप में संदर्भित किया जाता है- वे किनारों के सेट के साथ पूर्ण ग्राफ होते हैं परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त परिवार, समान रूप से विभाजित [[पूर्ण द्विदलीय ग्राफ]] K<sub>n,n</sub> और 2n शीर्षों पर क्राउन ग्राफ़ हैं। कई अन्य सममित रेखांकन को परिपत्र रेखांकन के रूप में वर्गीकृत किया जा सकता है। | ||
[[राडो ग्राफ]] सममित ग्राफ का उदाहरण | [[राडो ग्राफ]] सममित ग्राफ का उदाहरण है जिसमें अनंत रूप से कई कोने और अनंत डिग्री होती है। | ||
=== घन सममित रेखांकन === | === घन सममित रेखांकन === | ||
समरूपता की स्थिति को प्रतिबंध के साथ जोड़कर कि ग्राफ़ क्यूबिक | समरूपता की स्थिति को प्रतिबंध के साथ जोड़कर कि ग्राफ़ क्यूबिक हो (अर्थात सभी कोने में डिग्री 3 है) अधिक स्थिर स्थिति उत्पन्न करता है, और ऐसे ग्राफ़ सूचीबद्ध होने के लिए पर्याप्त दुर्लभ हैं। उन सभी के शीर्षों की संख्या सम है। फोस्टर जनगणना और इसके विस्तार ऐसी सूचियां प्रदान करते हैं।<ref>[[Marston Conder]], ''[http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps Trivalent symmetric graphs on up to 768 vertices],'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63</ref> फोस्टर जनगणना 1930 के दशक में रोनाल्ड एम. फोस्टर द्वारा प्रारंभ की गई थी, जबकि वह [[बेल लैब्स]] द्वारा नियोजित थे,<ref>Foster, R. M. "Geometrical Circuits of Electrical Networks." ''[[Transactions of the American Institute of Electrical Engineers]]'' '''51''', 309–317, 1932.</ref> और 1988 में (जब फोस्टर 92 वर्ष के थे)<ref name="biggs"/> तत्कालीन वर्तमान फोस्टर जनगणना (512 तक सभी घन सममित रेखांकन को सूचीबद्ध करना) को पुस्तक रूप में प्रकाशित किया गया था।<ref>"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) {{isbn|0-919611-19-2}}</ref> सूची में पूर्व तेरह आइटम क्यूबिक सिमिट्रिक ग्राफ़ हैं जिनमें 30 कोने हैं<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., "[http://mathworld.wolfram.com/CubicSymmetricGraph.html Cubic Symmetric Graph]", from Wolfram MathWorld.</ref>(इनमें से दस दूरी-संक्रमणीय हैं; अपवाद संकेत के अनुसार हैं): | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 62: | Line 62: | ||
== गुण == | == गुण == | ||
सममित ग्राफ की वर्टेक्स-कनेक्टिविटी सदैव नियमित ग्राफ d के समान होती है।<ref name="babai" />इसके विपरीत, वर्टेक्स-ट्रांसिटिव ग्राफ़ के लिए सामान्य रूप से, वर्टेक्स-कनेक्टिविटी 2(d + 1)/3 से नीचे होती है।<ref name="godsil" /> | |||
डिग्री 3 या उससे अधिक के टी-सकर्मक ग्राफ में कम से कम 2(t – 1) गर्थ (ग्राफ़ सिद्धांत) होता है। चूँकि , t ≥ 8 के लिए डिग्री 3 या उससे अधिक का कोई परिमित टी-संक्रमणीय ग्राफ़ नहीं है। डिग्री ठीक 3 (घन सममित ग्राफ़) होने के मामले में, t ≥ 6 के लिए कोई नहीं है। | डिग्री 3 या उससे अधिक के टी-सकर्मक ग्राफ में कम से कम 2(t – 1) गर्थ (ग्राफ़ सिद्धांत) होता है। चूँकि , t ≥ 8 के लिए डिग्री 3 या उससे अधिक का कोई परिमित टी-संक्रमणीय ग्राफ़ नहीं है। डिग्री ठीक 3 (घन सममित ग्राफ़) होने के मामले में, t ≥ 6 के लिए कोई नहीं है। | ||
Revision as of 23:39, 10 May 2023
ग्राफ सिद्धांत के गणितीय क्षेत्र में, ग्राफ (असतत गणित) G सममित (या आर्क-संक्रमणीय) है, यदि G के आसन्न शीर्षों (ग्राफ सिद्धांत) u1—v1 और u2—v2 के किसी भी दो जोड़े का ऑटोमोर्फिज्म है:
ऐसा है कि
- और [1]
दूसरे शब्दों में, ग्राफ़ सममित होता है यदि इसका ऑटोमोर्फिज़्म समूह आसन्न शीर्षों के क्रमित युग्मों पर सकर्मक रूप से कार्य करता है (अर्थात, किनारों पर दिशा के रूप में माना जाता है)।[2] इस प्रकार के ग्राफ को कभी-कभी 1-arc सकर्मक या ध्वज-सकर्मक भी कहा जाता है।[2][3]
परिभाषा के अनुसार (u1 और u2), पृथक शीर्षों के बिना सममित ग्राफ़ भी शीर्ष-संक्रमणीय होना चाहिए।[1]चूंकि ऊपर दी गई परिभाषा एक किनारे से दूसरे किनारे को मैप करती है, सममित ग्राफ भी बढ़त-सकर्मक ग्राफ होना चाहिए। चूँकि, किनारे-संक्रमणीय ग्राफ को सममित होने की आवश्यकता नहीं है, क्योंकि a—b, c—d को मैप कर सकता है, किंतु d—c को नहीं मैप कर सकता है। स्टार (ग्राफ सिद्धांत) शीर्ष-संक्रमणीय या सममित हुए बिना बढ़त-संक्रमणीय होने का सरल उदाहरण है। और उदाहरण के रूप में, अर्ध-सममित रेखांकन बढ़त-सकर्मक और नियमित ग्राफ हैं, किंतु शीर्ष-संक्रमणीय नहीं हैं।
| 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 | |
प्रत्येक कनेक्टिविटी (ग्राफ सिद्धांत) सममित ग्राफ इस प्रकार शीर्ष-सकर्मक और बढ़त-संक्रमणीय दोनों होना चाहिए, और विषम (गणित) डिग्री के ग्राफ के लिए विलोम सत्य है।[3] चूँकि, समान (गणित) की डिग्री के लिए, जुड़े हुए ग्राफ़ उपस्थित हैं जो शीर्ष-सकर्मक और बढ़त-संक्रमणीय हैं, किंतु सममित नहीं हैं।[4] ऐसे रेखांकन को अर्ध-संक्रमणीय ग्राफ कहा जाता है।[5] सबसे छोटा जुड़ा हुआ अर्ध-संक्रमणीयहोल्ट का ग्राफ है, जिसमें डिग्री 4 और 27 शीर्ष हैं।[1][6] भ्रामक रूप से, कुछ लेखक शब्द सममित ग्राफ का उपयोग ऐसे ग्राफ के लिए करते हैं, जो आर्क-सममित ग्राफ के अतिरिक्त शीर्ष-सकर्मक और बढ़त-संक्रमणीय है। इस प्रकार की परिभाषा में अर्ध-संक्रमणीय ग्राफ सम्मिलित होंगे, जिन्हें उपरोक्त परिभाषा के अंतर्गत बाहर रखा गया है।
दूरी-सकर्मक ग्राफ वह है जहां आसन्न शीर्षों के जोड़े पर विचार करने के अतिरिक्त (अर्थात 1 की दूरी पर कोने), परिभाषा में दो जोड़े सम्मिलित हैं, प्रत्येक दूरी के अतिरिक्त हैं। इस प्रकार के रेखांकन परिभाषा के अनुसार स्वचालित रूप से सममित होते हैं।[1]
t-arc को t + 1 कोने के अनुक्रम के रूप में परिभाषित किया गया है, जैसे कि अनुक्रम में कोई भी निरंतर दो कोने आसन्न हैं, और किसी भी दोहराए जाने वाले कोने 2 चरणों से अधिक की दूरी है। t-transitive ग्राफ ऐसा ग्राफ है जैसे कि ऑटोमोर्फिज्म समूह t-arcs पर सकर्मक रूप से कार्य करता है, किंतु (t + 1)-arcs पर नहीं कार्य करता है। चूंकि 1-arcs केवल किनारे हैं, डिग्री 3 या उससे अधिक के प्रत्येक सममित ग्राफ को कुछ t के लिए t-transitive होना चाहिए, और t के मान का उपयोग सममित ग्राफ को आगे वर्गीकृत करने के लिए किया जा सकता है। उदाहरण के लिए घन 2-transitive है।[1]
ध्यान दें कि परंपरागत रूप से "सममित ग्राफ" शब्द असममित ग्राफ शब्द का पूरक नहीं है, क्योंकि उत्तरार्द्ध ऐसे ग्राफ को संदर्भित करता है जिसमें कोई गैर-समरूप समरूपता नहीं है।
उदाहरण
किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार चक्र ग्राफ (2 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: घनक्षेत्र, ऑक्टाहेड्रोन, आईकोसैहेड्रोन, द्वादशफ़लक, [[क्यूबोक्टाहेड्रोन]] और इकोसिडोडेकेड्रॉन हैं। क्यूब का n आयामों तक विस्तार हाइपरक्यूब ग्राफ देता है (2n शीर्ष और डिग्री n)। इसी प्रकार ऑक्टाहेड्रॉन से n आयामों का विस्तार क्रॉस-पॉलीटोप्स के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी कॉकटेल पार्टी ग्राफ के रूप में संदर्भित किया जाता है- वे किनारों के सेट के साथ पूर्ण ग्राफ होते हैं परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त परिवार, समान रूप से विभाजित पूर्ण द्विदलीय ग्राफ Kn,n और 2n शीर्षों पर क्राउन ग्राफ़ हैं। कई अन्य सममित रेखांकन को परिपत्र रेखांकन के रूप में वर्गीकृत किया जा सकता है।
राडो ग्राफ सममित ग्राफ का उदाहरण है जिसमें अनंत रूप से कई कोने और अनंत डिग्री होती है।
घन सममित रेखांकन
समरूपता की स्थिति को प्रतिबंध के साथ जोड़कर कि ग्राफ़ क्यूबिक हो (अर्थात सभी कोने में डिग्री 3 है) अधिक स्थिर स्थिति उत्पन्न करता है, और ऐसे ग्राफ़ सूचीबद्ध होने के लिए पर्याप्त दुर्लभ हैं। उन सभी के शीर्षों की संख्या सम है। फोस्टर जनगणना और इसके विस्तार ऐसी सूचियां प्रदान करते हैं।[7] फोस्टर जनगणना 1930 के दशक में रोनाल्ड एम. फोस्टर द्वारा प्रारंभ की गई थी, जबकि वह बेल लैब्स द्वारा नियोजित थे,[8] और 1988 में (जब फोस्टर 92 वर्ष के थे)[1] तत्कालीन वर्तमान फोस्टर जनगणना (512 तक सभी घन सममित रेखांकन को सूचीबद्ध करना) को पुस्तक रूप में प्रकाशित किया गया था।[9] सूची में पूर्व तेरह आइटम क्यूबिक सिमिट्रिक ग्राफ़ हैं जिनमें 30 कोने हैं[10][11](इनमें से दस दूरी-संक्रमणीय हैं; अपवाद संकेत के अनुसार हैं):
| सिरे | व्यास | v | ग्राफ़ | टिप्पणियाँ |
|---|---|---|---|---|
| 4 | 1 | 3 | पूर्ण ग्राफ़ K4 | दूरी-सकर्मक, 2-चाप-सकर्मक |
| 6 | 2 | 4 | पूर्ण द्विदलीय ग्राफ K3,3 | दूरी-सकर्मक, 3-चाप-सकर्मक |
| 8 | 3 | 4 | घन के शीर्ष और किनारे | दूरी-सकर्मक, 2-चाप-सकर्मक |
| 10 | 2 | 5 | पीटरसन ग्राफ | दूरी-सकर्मक, 3-चाप-सकर्मक |
| 14 | 3 | 6 | हीवुड ग्राफ | दूरी-सकर्मक, 4-चाप-सकर्मक |
| 16 | 4 | 6 | मोबियस-कैंटर ग्राफ | 2-चाप-सकर्मक |
| 18 | 4 | 6 | पप्पुस ग्राफ | दूरी-सकर्मक, 3-चाप-सकर्मक |
| 20 | 5 | 5 | द्वादशफलक के शीर्ष और किनारे | दूरी-सकर्मक, 2-चाप-सकर्मक |
| 20 | 5 | 6 | देसरगेस ग्राफ | दूरी-सकर्मक, 3-चाप-सकर्मक |
| 24 | 4 | 6 | नाउरू ग्राफ (सामान्यीकृत पीटरसन ग्राफ G(12,5)) | 2-चाप-सकर्मक |
| 26 | 5 | 6 | F26A ग्राफ[11] | 1-चाप-सकर्मक |
| 28 | 4 | 7 | कॉक्सेटर ग्राफ | दूरी-सकर्मक, 3-चाप-सकर्मक |
| 30 | 4 | 8 | टुट्टे-कॉक्सेटर ग्राफ | दूरी-सकर्मक, 5-चाप-सकर्मक |
अन्य प्रसिद्ध घन सममित रेखांकन डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ हैं। फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ के साथ ऊपर सूचीबद्ध दस दूरी-सकर्मक ग्राफ, केवल क्यूबिक दूरी-सकर्मक ग्राफ हैं।
गुण
सममित ग्राफ की वर्टेक्स-कनेक्टिविटी सदैव नियमित ग्राफ d के समान होती है।[3]इसके विपरीत, वर्टेक्स-ट्रांसिटिव ग्राफ़ के लिए सामान्य रूप से, वर्टेक्स-कनेक्टिविटी 2(d + 1)/3 से नीचे होती है।[2]
डिग्री 3 या उससे अधिक के टी-सकर्मक ग्राफ में कम से कम 2(t – 1) गर्थ (ग्राफ़ सिद्धांत) होता है। चूँकि , t ≥ 8 के लिए डिग्री 3 या उससे अधिक का कोई परिमित टी-संक्रमणीय ग्राफ़ नहीं है। डिग्री ठीक 3 (घन सममित ग्राफ़) होने के मामले में, t ≥ 6 के लिए कोई नहीं है।
यह भी देखें
- बीजगणितीय ग्राफ सिद्धांत
- नामित रेखांकन की गैलरी#सममितीय रेखांकन
- नियमित नक्शा (ग्राफ सिद्धांत)
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Biggs, Norman (1993). बीजगणितीय ग्राफ सिद्धांत (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.
- ↑ 2.0 2.1 2.2 Godsil, Chris; Royle, Gordon (2001). बीजगणितीय ग्राफ सिद्धांत. New York: Springer. p. 59. ISBN 0-387-95220-9.
- ↑ 3.0 3.1 3.2 Babai, L (1996). "Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, R; Grötschel, M; Lovász, L (eds.). कॉम्बिनेटरिक्स की हैंडबुक. Elsevier.
- ↑ Bouwer, Z. (1970). "वर्टेक्स और एज ट्रांजिटिव, लेकिन 1-ट्रांसिटिव ग्राफ नहीं". Canad. Math. Bull. 13: 231–237. doi:10.4153/CMB-1970-047-8.
- ↑ Gross, J.L. & Yellen, J. (2004). ग्राफ थ्योरी की पुस्तिका. CRC Press. p. 491. ISBN 1-58488-090-2.
- ↑ Holt, Derek F. (1981). "एक ग्राफ जो कोर सकर्मक है लेकिन चाप सकर्मक नहीं है". Journal of Graph Theory. 5 (2): 201–204. doi:10.1002/jgt.3190050210..
- ↑ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
- ↑ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
- ↑ "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
- ↑ Biggs, p. 148
- ↑ 11.0 11.1 Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.
बाहरी संबंध
- Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
- Trivalent (cubic) symmetric graphs on up to 10000 vertices. Marston Conder, 2011.
