सममित ग्राफ: Difference between revisions
(Created page with "{{short description|Graph in which all ordered pairs of linked nodes are automorphic}} thumb|200px|[[पीटरसन ग्राफ एक (घ...") |
No edit summary |
||
| Line 21: | Line 21: | ||
== उदाहरण == | == उदाहरण == | ||
किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार [[चक्र ग्राफ]]़ (2 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: [[ घनक्षेत्र ]], ऑक्टाहेड्रोन, [[विंशतिफलक]], [[द्वादशफ़लक]], [[cub[[octahedron]]]] और [[icosidodecahedron]] क्यूब से एन आयामों का विस्तार हाइपरक्यूब ग्राफ देता है (2 के साथ<sup>n</sup> शीर्ष और डिग्री n). इसी तरह ऑक्टाहेड्रॉन से एन आयामों का विस्तार [[ क्रॉस-पॉलीटॉप ]]्स के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी [[कॉकटेल पार्टी ग्राफ]] के रूप में संदर्भित किया जाता है - वे किनारों के एक सेट के साथ पूर्ण ग्राफ होते हैं एक परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त परिवार, समान रूप से विभाजित [[पूर्ण द्विदलीय ग्राफ]]़ हैं K<sub>n,n</sub> और 2n शीर्षों पर क्राउन रेखांकन। कई अन्य सममित रेखांकन को परिपत्र रेखांकन (लेकिन सभी नहीं) के रूप में वर्गीकृत किया जा सकता है। | किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार [[चक्र ग्राफ]]़ (2 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: [[ घनक्षेत्र ]], ऑक्टाहेड्रोन, [[विंशतिफलक]], [[द्वादशफ़लक]], [[cub[[octahedron]]]] और [[icosidodecahedron]] क्यूब से एन आयामों का विस्तार हाइपरक्यूब ग्राफ देता है (2 के साथ<sup>n</sup> शीर्ष और डिग्री n). इसी तरह ऑक्टाहेड्रॉन से एन आयामों का विस्तार [[ क्रॉस-पॉलीटॉप ]]्स के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी [[कॉकटेल पार्टी ग्राफ]] के रूप में संदर्भित किया जाता है - वे किनारों के एक सेट के साथ पूर्ण ग्राफ होते हैं एक परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त परिवार, समान रूप से विभाजित [[पूर्ण द्विदलीय ग्राफ]]़ हैं K<sub>n,n</sub> और 2n शीर्षों पर क्राउन रेखांकन। कई अन्य सममित रेखांकन को परिपत्र रेखांकन (लेकिन सभी नहीं) के रूप में वर्गीकृत किया जा सकता है। | ||
Revision as of 22:21, 10 May 2023
ग्राफ सिद्धांत के गणित क्षेत्र में, एक ग्राफ (असतत गणित) G सममित (या आर्क-संक्रमणीय) है, अगर आसन्न वर्टेक्स (ग्राफ सिद्धांत) के किसी भी दो जोड़े दिए गए हैं u1—v1 और u2—v2 का G, एक ग्राफ ऑटोमोर्फिज्म है
ऐसा है कि
- और [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]
A t-arc को अनुक्रम के रूप में परिभाषित किया गया है t + 1 कोने, जैसे कि अनुक्रम में कोई भी लगातार दो कोने आसन्न हैं, और किसी भी दोहराए गए कोने के बीच 2 चरणों से अधिक की दूरी है। एt-transitive ग्राफ एक ऐसा ग्राफ है जिस पर ऑटोमोर्फिज्म समूह सकर्मक रूप से कार्य करता है t-arcs, लेकिन चालू नहीं (t + 1)-arcs. तब से 1-arcs केवल किनारे हैं, डिग्री 3 या उससे अधिक का प्रत्येक सममित ग्राफ होना चाहिए t-transitive कुछ के लिए t, और का मान t का उपयोग सममित रेखांकन को और वर्गीकृत करने के लिए किया जा सकता है। घन है 2-transitive, उदाहरण के लिए।[1]
ध्यान दें कि परंपरागत रूप से शब्द सममित ग्राफ शब्द असममित ग्राफ का पूरक नहीं है, क्योंकि बाद वाला एक ऐसे ग्राफ को संदर्भित करता है जिसमें कोई गैर-समरूप समरूपता नहीं है।
उदाहरण
किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार चक्र ग्राफ़ (2 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: घनक्षेत्र , ऑक्टाहेड्रोन, विंशतिफलक, द्वादशफ़लक, [[cuboctahedron]] और icosidodecahedron क्यूब से एन आयामों का विस्तार हाइपरक्यूब ग्राफ देता है (2 के साथn शीर्ष और डिग्री n). इसी तरह ऑक्टाहेड्रॉन से एन आयामों का विस्तार क्रॉस-पॉलीटॉप ्स के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी कॉकटेल पार्टी ग्राफ के रूप में संदर्भित किया जाता है - वे किनारों के एक सेट के साथ पूर्ण ग्राफ होते हैं एक परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त परिवार, समान रूप से विभाजित पूर्ण द्विदलीय ग्राफ़ हैं Kn,n और 2n शीर्षों पर क्राउन रेखांकन। कई अन्य सममित रेखांकन को परिपत्र रेखांकन (लेकिन सभी नहीं) के रूप में वर्गीकृत किया जा सकता है।
राडो ग्राफ एक सममित ग्राफ का एक उदाहरण बनाता है जिसमें अनंत रूप से कई कोने और अनंत डिग्री होती है
घन सममित रेखांकन
समरूपता की स्थिति को प्रतिबंध के साथ जोड़कर कि ग्राफ़ क्यूबिक ग्राफ़ (अर्थात सभी कोने में डिग्री 3 है) काफी मजबूत स्थिति पैदा करता है, और ऐसे ग्राफ़ सूचीबद्ध होने के लिए पर्याप्त दुर्लभ हैं। उन सभी के शीर्षों की संख्या सम है। फोस्टर जनगणना और इसके विस्तार ऐसी सूचियां प्रदान करते हैं।[7] फोस्टर जनगणना 1930 के दशक में आर. एम. फोस्टर|रोनाल्ड एम. फोस्टर द्वारा शुरू की गई थी, जबकि वह बेल लैब्स द्वारा नियोजित थे,[8] और 1988 में (जब फोस्टर 92 वर्ष के थे[1] तत्कालीन वर्तमान फोस्टर जनगणना (512 कोने तक सभी क्यूबिक सममित रेखांकन को सूचीबद्ध करना) को पुस्तक रूप में प्रकाशित किया गया था।[9] सूची में पहले तेरह आइटम क्यूबिक सिमिट्रिक ग्राफ़ हैं जिनमें 30 कोने तक हैं[10][11] (इनमें से दस दूरी-सकर्मक ग्राफ भी हैं। दूरी-सकर्मक; अपवाद संकेत के अनुसार हैं):
| Vertices | Diameter | Girth | Graph | Notes |
|---|---|---|---|---|
| 4 | 1 | 3 | The complete graph K4 | distance-transitive, 2-arc-transitive |
| 6 | 2 | 4 | The complete bipartite graph K3,3 | distance-transitive, 3-arc-transitive |
| 8 | 3 | 4 | The vertices and edges of the cube | distance-transitive, 2-arc-transitive |
| 10 | 2 | 5 | The Petersen graph | distance-transitive, 3-arc-transitive |
| 14 | 3 | 6 | The Heawood graph | distance-transitive, 4-arc-transitive |
| 16 | 4 | 6 | The Möbius–Kantor graph | 2-arc-transitive |
| 18 | 4 | 6 | The Pappus graph | distance-transitive, 3-arc-transitive |
| 20 | 5 | 5 | The vertices and edges of the dodecahedron | distance-transitive, 2-arc-transitive |
| 20 | 5 | 6 | The Desargues graph | distance-transitive, 3-arc-transitive |
| 24 | 4 | 6 | The Nauru graph (the generalized Petersen graph G(12,5)) | 2-arc-transitive |
| 26 | 5 | 6 | The F26A graph[11] | 1-arc-transitive |
| 28 | 4 | 7 | The Coxeter graph | distance-transitive, 3-arc-transitive |
| 30 | 4 | 8 | The Tutte–Coxeter graph | distance-transitive, 5-arc-transitive |
अन्य प्रसिद्ध घन सममित रेखांकन डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ हैं। फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ के साथ ऊपर सूचीबद्ध दस दूरी-सकर्मक ग्राफ, केवल क्यूबिक दूरी-सकर्मक ग्राफ हैं।
गुण
कनेक्टिविटी (ग्राफ थ्योरी) | सममित ग्राफ की वर्टेक्स-कनेक्टिविटी हमेशा नियमित ग्राफ डी के बराबर होती है।[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.
