सममित ग्राफ

पीटरसन ग्राफ (घन ग्राफ) सममित ग्राफ है। आसन्न शीर्षों की किसी भी जोड़ी को ग्राफ ऑटोमोर्फिज्म द्वारा दूसरे से मैप किया जा सकता है, क्योंकि किसी भी पाँच-शीर्ष रिंग को किसी अन्य से मैप किया जा सकता है।

ग्राफ सिद्धांत के गणितीय क्षेत्र में, ग्राफ (असतत गणित) $G$ सममित (या आर्क-संक्रमणीय) है, यदि $G$ के आसन्न शीर्ष (ग्राफ सिद्धांत) $u 1 — v 1$ और $u 2 — v 2$ के किसी भी दो जोड़े का ऑटोमोर्फिज्म है: तो

f:V(G)\rightarrow V(G)

जैसे-

f(u_{1})=u_{2}

और

f(v_{1})=v_{2}.

^[1]

दूसरे शब्दों में, ग्राफ़ सममित होता है यदि इसका ऑटोमोर्फिज़्म समूह आसन्न शीर्षों के क्रमित युग्मों पर संक्रमणीय रूप से कार्य करता है (अर्थात, कोरों पर दिशा के रूप में माना जाता है)।^[2] इस प्रकार के ग्राफ को कभी-कभी 1-आर्क संक्रमणीय या ध्वज-संक्रमणीय भी कहा जाता है।^[2]^[3]

परिभाषा के अनुसार ( $u 1$ और $u 2$ ), पृथक शीर्षों के बिना सममित ग्राफ़ भी शीर्ष-संक्रमणीय होना चाहिए।^[1] चूंकि ऊपर दी गई परिभाषा एक कोर से दूसरे कोर को मैप करती है, सममित ग्राफ भी कोर-संक्रमणीय ग्राफ होना चाहिए। चूँकि, कोर-संक्रमणीय ग्राफ को सममित होने की आवश्यकता नहीं है, क्योंकि $a—b$ , $c—d$ को मैप कर सकता है, किंतु $d—c$ को मैप नहीं कर सकता है। स्टार (ग्राफ सिद्धांत) शीर्ष-संक्रमणीय या सममित हुए बिना कोर-संक्रमणीय होने का सरल उदाहरण है। उदाहरण के रूप में, अर्ध-सममित रेखांकन कोर-संक्रमणीय और नियमित ग्राफ हैं, किंतु शीर्ष-संक्रमणीय नहीं हैं।

प्रत्येक कनेक्टिविटी (ग्राफ सिद्धांत) सममित ग्राफ इस प्रकार शीर्ष-संक्रमणीय और कोर-संक्रमणीय दोनों होना चाहिए, और विषम (गणित) डिग्री के ग्राफ के लिए विलोम सत्य है।^[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 आयामों तक विस्तार हाइपरक्यूब ग्राफ देता है (2ⁿ शीर्ष और डिग्री n)। इसी प्रकार ऑक्टाहेड्रॉन से n आयामों का विस्तार क्रॉस-पॉलीटोप्स के ग्राफ देता है, ग्राफ के इस परिवार (2n कोने और डिग्री 2n-2 के साथ) को कभी-कभी कॉकटेल पार्टी ग्राफ के रूप में संदर्भित किया जाता है- वे किनारों के सेट के साथ पूर्ण ग्राफ होते हैं परिपूर्ण मिलान को हटा दिया गया। वर्टिकल 2n की सम संख्या वाले सममित ग्राफ़ के अतिरिक्त सदस्य, समान रूप से विभाजित पूर्ण द्विदलीय ग्राफ K_n,n और 2n शीर्षों पर क्राउन ग्राफ़ हैं। कई अन्य सममित रेखांकन को परिपत्र रेखांकन के रूप में वर्गीकृत किया जा सकता है।

राडो ग्राफ सममित ग्राफ का उदाहरण है जिसमें अनंत रूप से कई कोने और अनंत डिग्री होती है।

घन सममित रेखांकन

समरूपता की स्थिति को प्रतिबंध के साथ जोड़कर कि ग्राफ़ क्यूबिक हो (अर्थात सभी कोने में डिग्री 3 है) अधिक स्थिर स्थिति उत्पन्न करता है, और ऐसे ग्राफ़ सूचीबद्ध होने के लिए पर्याप्त दुर्लभ हैं। उन सभी के शीर्षों की संख्या सम है। फोस्टर जनगणना और इसके विस्तार ऐसी सूचियां प्रदान करते हैं।^[7] फोस्टर जनगणना 1930 के दशक में रोनाल्ड एम. फोस्टर द्वारा प्रारंभ की गई थी, जबकि वह बेल लैब्स द्वारा नियोजित थे,^[8] और 1988 में (जब फोस्टर 92 वर्ष के थे)^[1] तत्कालीन वर्तमान फोस्टर जनगणना (512 तक सभी घन सममित रेखांकन को सूचीबद्ध करना) को पुस्तक रूप में प्रकाशित किया गया था।^[9] सूची में पूर्व तेरह आइटम क्यूबिक सिमिट्रिक ग्राफ़ हैं जिनमें 30 कोने हैं^[10]^[11](इनमें से दस दूरी-संक्रमणीय हैं; अपवाद संकेत के अनुसार हैं):

सिरे	व्यास	v	ग्राफ़	टिप्पणियाँ
4	1	3	पूर्ण ग्राफ़ K₄	दूरी-संक्रमणीय, 2-कोर-संक्रमणीय
6	2	4	पूर्ण द्विदलीय ग्राफ K_3,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	एफ26ए ग्राफ^[11]	1-कोर-संक्रमणीय
28	4	7	कॉक्सेटर ग्राफ	दूरी-संक्रमणीय, 3-कोर-संक्रमणीय
30	4	8	टुट्टे-कॉक्सेटर ग्राफ	दूरी-संक्रमणीय, 5-कोर-संक्रमणीय

अन्य प्रसिद्ध घन सममित रेखांकन डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ हैं। फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ के साथ ऊपर सूचीबद्ध दस दूरी-संक्रमणीय ग्राफ, केवल क्यूबिक दूरी-संक्रमणीय ग्राफ हैं।

गुण

सममित ग्राफ की शीर्ष-कनेक्टिविटी सदैव नियमित ग्राफ d के समान होती है।^[3] इसके विपरीत, शीर्ष-ट्रांसिटिव ग्राफ़ के लिए सामान्य रूप से, शीर्ष-कनेक्टिविटी 2(d + 1)/3 से नीचे होती है।^[2]

डिग्री 3 या उससे अधिक के t-संक्रमणीय ग्राफ में कम से कम 2(t – 1) का घेरा होता है। चूँकि, t ≥ 8 के लिए डिग्री 3 या उससे अधिक का कोई परिमित t-संक्रमणीय ग्राफ़ नहीं है। डिग्री 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.

[biggs-1] 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.

[godsil-2] 2.0 ^2.1 ^2.2 Godsil, Chris; Royle, Gordon (2001). बीजगणितीय ग्राफ सिद्धांत. New York: Springer. p. 59. ISBN 0-387-95220-9.

[babai-3] 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.

[4] Bouwer, Z. (1970). "वर्टेक्स और एज ट्रांजिटिव, लेकिन 1-ट्रांसिटिव ग्राफ नहीं". Canad. Math. Bull. 13: 231–237. doi:10.4153/CMB-1970-047-8.

[handbook-5] Gross, J.L. & Yellen, J. (2004). ग्राफ थ्योरी की पुस्तिका. CRC Press. p. 491. ISBN 1-58488-090-2.

[6] Holt, Derek F. (1981). "एक ग्राफ जो कोर सकर्मक है लेकिन चाप सकर्मक नहीं है". Journal of Graph Theory. 5 (2): 201–204. doi:10.1002/jgt.3190050210..

[7] Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63

[8] Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.

[9] "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

[10] Biggs, p. 148

[F26A-11] 11.0 ^11.1 Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph\|t-transitive, $t \geq 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

सममित ग्राफ

Contents

उदाहरण

घन सममित रेखांकन

गुण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation menu

Search