सममित ग्राफ: Difference between revisions

Revision as of 23:09, 10 May 2023

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

ग्राफ सिद्धांत के गणितीय क्षेत्र में, ग्राफ (असतत गणित) $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-arc सकर्मक या ध्वज-सकर्मक भी कहा जाता है।^[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 डिग्री के) और पूर्ण ग्राफ़ हैं। आगे के सममित रेखांकन नियमित और अर्ध-नियमित पॉलीहेड्रा के कोने और किनारों से बनते हैं: घनक्षेत्र , ऑक्टाहेड्रोन, विंशतिफलक, द्वादशफ़लक, [[cuboctahedron]] और icosidodecahedron क्यूब से एन आयामों का विस्तार हाइपरक्यूब ग्राफ देता है (2 के साथⁿ शीर्ष और डिग्री 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	F26A ग्राफ^[11]	1-चाप-सकर्मक
28	4	7	कॉक्सेटर ग्राफ	दूरी-सकर्मक, 3-चाप-सकर्मक
30	4	8	टुट्टे-कॉक्सेटर ग्राफ	दूरी-सकर्मक, 5-चाप-सकर्मक

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

गुण

कनेक्टिविटी (ग्राफ थ्योरी) | सममित ग्राफ की वर्टेक्स-कनेक्टिविटी हमेशा नियमित ग्राफ डी के बराबर होती है।^[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.

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

@@ Line 1: / Line 1: @@
 {{short description|Graph in which all ordered pairs of linked nodes are automorphic}}
-[[File:Petersen1 tiny.svg|thumb|200px|[[पीटरसन ग्राफ]] (घन ग्राफ) सममित ग्राफ है। आसन्न शीर्षों की किसी भी जोड़ी को [[ग्राफ ऑटोमोर्फिज्म]] द्वारा दूसरे से मैप किया जा सकता है, क्योंकि किसी भी पाँच-शीर्ष रिंग को किसी अन्य से मैप किया जा सकता है।]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, [[ग्राफ (असतत गणित)]] {{mvar|G}} सममित (या आर्क-संक्रमणीय) है, यदि आसन्न वर्टेक्स (ग्राफ सिद्धांत) के किसी भी दो जोड़े दिए गए हैं {{math|''u''{{sub|1}}—''v''{{sub|1}}}} और {{math|''u''{{sub|2}}—''v''{{sub|2}}}} का {{mvar|G}}, ग्राफ ऑटोमोर्फिज्म है
+[[File:Petersen1 tiny.svg|thumb|200px|[[पीटरसन ग्राफ]] (घन ग्राफ) सममित ग्राफ है। आसन्न शीर्षों की किसी भी जोड़ी को [[ग्राफ ऑटोमोर्फिज्म]] द्वारा दूसरे से मैप किया जा सकता है, क्योंकि किसी भी पाँच-शीर्ष रिंग को किसी अन्य से मैप किया जा सकता है।]][[ग्राफ सिद्धांत]] के गणितीय क्षेत्र में, [[ग्राफ (असतत गणित)]] {{mvar|G}} सममित (या आर्क-संक्रमणीय) है, यदि {{mvar|G}} के आसन्न शीर्षों (ग्राफ सिद्धांत) {{math|''u''{{sub|1}}—''v''{{sub|1}}}} और {{math|''u''{{sub|2}}—''v''{{sub|2}}}} के किसी भी दो जोड़े का ऑटोमोर्फिज्म है:
 :<math>f : V(G) \rightarrow V(G)</math>
@@ Line 6: / Line 6: @@
 :<math>f(u_1) = u_2</math> और <math>f(v_1) = v_2.</math><ref name="biggs">{{cite book | author=Biggs, Norman | title=बीजगणितीय ग्राफ सिद्धांत| edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | pages=118–140 | isbn=0-521-45897-8}}</ref>
-दूसरे शब्दों में, ग्राफ़ सममित होता है यदि इसका ऑटोमोर्फिज़्म समूह ग्रुप_एक्शन#टाइप_ऑफ़_एक्शन को आसन्न कोने के आदेशित जोड़े पर कार्य करता है (अर्थात, किनारों पर दिशा के रूप में माना जाता है)।<ref name="godsil">{{cite book |first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=बीजगणितीय ग्राफ सिद्धांत|url=https://archive.org/details/algebraicgraphth00gods|url-access=limited| location=New York| publisher=Springer | year=2001 | page=[https://archive.org/details/algebraicgraphth00gods/page/n79 59] | isbn=0-387-95220-9}}</ref> ऐसे ग्राफ को कभी-कभी भी कहा जाता है{{nowrap|1-arc}}- सकर्मक<ref name="godsil"/>या ध्वज-सकर्मक।<ref name="babai">{{Cite book | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last =  Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = कॉम्बिनेटरिक्स की हैंडबुक| contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf | year = 1996 | publisher = Elsevier}}</ref>
+दूसरे शब्दों में, ग्राफ़ सममित होता है यदि इसका ऑटोमोर्फिज़्म समूह आसन्न शीर्षों के क्रमित युग्मों पर सकर्मक रूप से कार्य करता है (अर्थात, किनारों पर दिशा के रूप में माना जाता है)।<ref name="godsil">{{cite book |first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=बीजगणितीय ग्राफ सिद्धांत|url=https://archive.org/details/algebraicgraphth00gods|url-access=limited| location=New York| publisher=Springer | year=2001 | page=[https://archive.org/details/algebraicgraphth00gods/page/n79 59] | isbn=0-387-95220-9}}</ref> इस प्रकार के ग्राफ को कभी-कभी {{nowrap|1-arc}} सकर्मक या ध्वज-सकर्मक भी कहा जाता है।<ref name="godsil"/><ref name="babai">{{Cite book | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last =  Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = कॉम्बिनेटरिक्स की हैंडबुक| contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf | year = 1996 | publisher = Elsevier}}</ref>
-परिभाषा के अनुसार (अनदेखा करना {{math|''u''{{sub|1}}}} और {{math|''u''{{sub|2}}}}), [[ पृथक शिखर ]] के बिना सिमेट्रिक ग्राफ़ भी [[वर्टेक्स-सकर्मक ग्राफ]]|वर्टेक्स-ट्रांसिटिव होना चाहिए।<ref name="biggs" />चूंकि ऊपर दी गई परिभाषा किनारे से दूसरे किनारे को मैप करती है, सममित ग्राफ भी [[बढ़त-सकर्मक ग्राफ]]|एज-ट्रांसिटिव होना चाहिए। हालांकि, किनारे-सकर्मक ग्राफ को सममित होने की आवश्यकता नहीं है, क्योंकि {{mvar|a—b}} मैप कर सकता है {{mvar|c—d}}, लेकिन नहीं {{mvar|d—c}}. [[ तारा (ग्राफ सिद्धांत) ]] शीर्ष-संक्रमणीय या सममित हुए बिना बढ़त-संक्रमणीय होने का सरल उदाहरण है। और उदाहरण के रूप में, अर्ध-सममित रेखांकन बढ़त-सकर्मक और [[नियमित ग्राफ]] हैं, लेकिन वर्टेक्स-संक्रमणीय नहीं हैं।
+परिभाषा के अनुसार ({{math|''u''{{sub|1}}}} और {{math|''u''{{sub|2}}}}), [[ पृथक शिखर |पृथक शीर्षों]] के बिना सममित ग्राफ़ भी [[वर्टेक्स-सकर्मक ग्राफ|शीर्ष-संक्रमणीय]] होना चाहिए।<ref name="biggs" />चूंकि ऊपर दी गई परिभाषा एक किनारे से दूसरे किनारे को मैप करती है, सममित ग्राफ भी [[बढ़त-सकर्मक ग्राफ]] होना चाहिए। चूँकि, किनारे-संक्रमणीय ग्राफ को सममित होने की आवश्यकता नहीं है, क्योंकि {{mvar|a—b}}, {{mvar|c—d}} को मैप कर सकता है, किंतु {{mvar|d—c}} को नहीं मैप कर सकता है।[[ तारा (ग्राफ सिद्धांत) | स्टार (ग्राफ सिद्धांत)]] शीर्ष-संक्रमणीय या सममित हुए बिना बढ़त-संक्रमणीय होने का सरल उदाहरण है। और उदाहरण के रूप में, अर्ध-सममित रेखांकन बढ़त-सकर्मक और [[नियमित ग्राफ]] हैं, किंतु शीर्ष-संक्रमणीय नहीं हैं।
   {{Graph families defined by their automorphisms}}
-प्रत्येक [[कनेक्टिविटी (ग्राफ सिद्धांत)]] सममित ग्राफ इस प्रकार शीर्ष-सकर्मक और बढ़त-संक्रमणीय दोनों होना चाहिए, और [[समता (गणित)]] डिग्री के ग्राफ के लिए बातचीत सही है।<ref name="babai" />  हालाँकि, समता (गणित) की डिग्री के लिए, जुड़े हुए ग्राफ़ मौजूद हैं जो वर्टेक्स-ट्रांसिटिव और एज-ट्रांसिटिव हैं, लेकिन सममित नहीं हैं।<ref>{{cite journal | last1=Bouwer | first1=Z. | title=वर्टेक्स और एज ट्रांजिटिव, लेकिन 1-ट्रांसिटिव ग्राफ नहीं| journal=[[Canad. Math. Bull.]] | volume=13 | pages=231&ndash;237 | date=1970 | doi=10.4153/CMB-1970-047-8 | doi-access=free}}</ref> इस तरह के रेखांकन को [[आधा-संक्रमणीय ग्राफ]] कहा जाता है। आधा-संक्रमणीय।<ref name="handbook">{{cite book |author1=Gross, J.L.  |author2=Yellen, J.  |name-list-style=amp | title=ग्राफ थ्योरी की पुस्तिका| publisher=CRC Press | year=2004| page=491 | isbn=1-58488-090-2}}</ref> सबसे छोटा जुड़ा हुआ आधा-संक्रमणीय ग्राफ होल्ट का ग्राफ है, जिसमें डिग्री 4 और 27 कोने हैं।<ref name="biggs" /><ref>{{Cite journal|title=एक ग्राफ जो कोर सकर्मक है लेकिन चाप सकर्मक नहीं है|first=Derek F.|last=Holt|journal=[[Journal of Graph Theory]]|volume=5|issue=2|pages=201–204|year=1981|doi=10.1002/jgt.3190050210}}.</ref> भ्रामक रूप से, कुछ लेखक शब्द सममित ग्राफ का उपयोग ऐसे ग्राफ के लिए करते हैं, जो आर्क-ट्रांसिटिव ग्राफ के बजाय वर्टेक्स-ट्रांसिटिव और एज-ट्रांसिटिव है। इस तरह की परिभाषा में अर्ध-संक्रमणीय ग्राफ शामिल होंगे, जिन्हें उपरोक्त परिभाषा के तहत बाहर रखा गया है।
+प्रत्येक [[कनेक्टिविटी (ग्राफ सिद्धांत)]] सममित ग्राफ इस प्रकार शीर्ष-सकर्मक और बढ़त-संक्रमणीय दोनों होना चाहिए, और [[समता (गणित)|विषम (गणित)]] डिग्री के ग्राफ के लिए विलोम सत्य है।<ref name="babai" />  चूँकि, समान (गणित) की डिग्री के लिए, जुड़े हुए ग्राफ़ उपस्थित हैं जो शीर्ष-सकर्मक और बढ़त-संक्रमणीय हैं, किंतु सममित नहीं हैं।<ref>{{cite journal | last1=Bouwer | first1=Z. | title=वर्टेक्स और एज ट्रांजिटिव, लेकिन 1-ट्रांसिटिव ग्राफ नहीं| journal=[[Canad. Math. Bull.]] | volume=13 | pages=231&ndash;237 | date=1970 | doi=10.4153/CMB-1970-047-8 | doi-access=free}}</ref> ऐसे रेखांकन को [[आधा-संक्रमणीय ग्राफ|अर्ध-संक्रमणीय ग्राफ]] कहा जाता है।<ref name="handbook">{{cite book |author1=Gross, J.L.  |author2=Yellen, J.  |name-list-style=amp | title=ग्राफ थ्योरी की पुस्तिका| publisher=CRC Press | year=2004| page=491 | isbn=1-58488-090-2}}</ref> सबसे छोटा जुड़ा हुआ अर्ध-संक्रमणीयहोल्ट का ग्राफ है, जिसमें डिग्री 4 और 27 शीर्ष हैं।<ref name="biggs" /><ref>{{Cite journal|title=एक ग्राफ जो कोर सकर्मक है लेकिन चाप सकर्मक नहीं है|first=Derek F.|last=Holt|journal=[[Journal of Graph Theory]]|volume=5|issue=2|pages=201–204|year=1981|doi=10.1002/jgt.3190050210}}.</ref> भ्रामक रूप से, कुछ लेखक शब्द सममित ग्राफ का उपयोग ऐसे ग्राफ के लिए करते हैं, जो आर्क-सममित ग्राफ के अतिरिक्त शीर्ष-सकर्मक और बढ़त-संक्रमणीय है। इस प्रकार की परिभाषा में अर्ध-संक्रमणीय ग्राफ सम्मिलित होंगे, जिन्हें उपरोक्त परिभाषा के अंतर्गत बाहर रखा गया है।
-[[दूरी-सकर्मक ग्राफ]] वह है जहां आसन्न शीर्षों के जोड़े पर विचार करने के बजाय (अर्थात 1 की दूरी पर कोने), परिभाषा में दो जोड़े जोड़े शामिल हैं, प्रत्येक ही दूरी के अलावा। इस तरह के रेखांकन स्वचालित रूप से सममित होते हैं, परिभाषा के अनुसार।<ref name="biggs" />
+[[दूरी-सकर्मक ग्राफ]] वह है जहां आसन्न शीर्षों के जोड़े पर विचार करने के अतिरिक्त (अर्थात 1 की दूरी पर कोने), परिभाषा में दो जोड़े सम्मिलित हैं, प्रत्येक दूरी के अतिरिक्त हैं। इस प्रकार के रेखांकन परिभाषा के अनुसार स्वचालित रूप से सममित होते हैं।<ref name="biggs" />
-A {{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 या उससे अधिक का प्रत्येक सममित ग्राफ होना चाहिए {{nowrap|{{mvar|t}}-transitive}} कुछ के लिए {{mvar|t}}, और का मान {{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" />
 ध्यान दें कि परंपरागत रूप से शब्द सममित ग्राफ शब्द [[असममित ग्राफ]] का पूरक नहीं है, क्योंकि बाद वाला ऐसे ग्राफ को संदर्भित करता है जिसमें कोई गैर-समरूप समरूपता नहीं है।
@@ Line 21: / Line 22: @@
 == उदाहरण ==
-किसी भी संख्या के शीर्षों के लिए सममित ग्राफ़ के दो मूल परिवार [[चक्र ग्राफ]]़ (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 शीर्षों पर क्राउन रेखांकन। कई अन्य सममित रेखांकन को परिपत्र रेखांकन (किंतुसभी नहीं) के रूप में वर्गीकृत किया जा सकता है।
 [[राडो ग्राफ]] सममित ग्राफ का उदाहरण बनाता है जिसमें अनंत रूप से कई कोने और अनंत डिग्री होती है
@@ Line 63: / Line 64: @@
 कनेक्टिविटी (ग्राफ थ्योरी) | सममित ग्राफ की वर्टेक्स-कनेक्टिविटी हमेशा नियमित ग्राफ डी के बराबर होती है।<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 के लिए कोई नहीं है।
 == यह भी देखें ==

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

Anonymous

Search

सममित ग्राफ: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:09, 10 May 2023

Contents

उदाहरण

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

गुण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सममित ग्राफ: Difference between revisions

Revision as of 23:09, 10 May 2023

उदाहरण

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

गुण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories