शीर्ष-संक्रमणीय ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
{{Graph families defined by their automorphisms}} | {{Graph families defined by their automorphisms}} | ||
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, एक '''शीर्ष-संक्रमणीय ग्राफ़''' एक ग्राफ़ {{mvar|G}} है जिसमें, {{mvar|G}} के किन्हीं दो शीर्षों {{math|''v''{{sub|1}}}} और {{math|''v''{{sub|2}}}} को देखते हुए, कुछ स्वचालितता होती है | |||
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, एक शीर्ष-संक्रमणीय ग्राफ़ एक ग्राफ़ {{mvar|G}} है जिसमें, {{mvar|G}} के किन्हीं दो शीर्षों {{math|''v''{{sub|1}}}} और {{math|''v''{{sub|2}}}} को देखते हुए, कुछ स्वचालितता होती है | |||
:<math>f : G \to G\ </math> | :<math>f : G \to G\ </math> | ||
| Line 14: | Line 13: | ||
== परिमित उदाहरण == | == परिमित उदाहरण == | ||
[[File:Tuncated tetrahedral graph.png|thumb|right|220px|काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक [[केली ग्राफ]] भी) बनाते हैं जो सममित ग्राफ नहीं है।]] | [[File:Tuncated tetrahedral graph.png|thumb|right|220px|काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक [[केली ग्राफ]] भी) बनाते हैं जो सममित ग्राफ नहीं है।]]परिमित शीर्ष-संक्रमणीय ग्राफ में सममित ग्राफ (जैसे [[पीटरसन ग्राफ]], [[हेवुड ग्राफ]] और [[प्लेटोनिक ठोस]] के शीर्ष और किनारे) सम्मिलित हैं। परिमित केली ग्राफ (जैसे [[घन-जुड़े चक्र]]) भी शीर्ष-संक्रमणीय हैं, जैसे कि [[आर्किमिडीयन ठोस]] के शीर्ष और किनारे हैं (चूँकि इनमें से केवल दो सममित हैं)। पोटोक्निक, स्पिगा और वेरेट ने अधिकतम 1280 शीर्षों पर सभी जुड़े हुए घन शीर्ष-संक्रमणीय ग्राफ़ की जनगणना का निर्माण किया है।<ref>{{citation|title=Cubic vertex-transitive graphs on up to 1280 vertices|author1=Potočnik P., Spiga P. |author2=Verret G. |name-list-style=amp |journal=Journal of Symbolic Computation |volume = 50 | year = 2013|pages = 465–477|doi=10.1016/j.jsc.2012.09.002|arxiv=1201.5317|s2cid=26705221 }}.</ref> | ||
चूँकि | |||
चूँकि प्रत्येक केली ग्राफ़ शीर्ष-संक्रमणीय है, अन्य शीर्ष-संक्रमणीय ग्राफ़ उपस्थित हैं जो केली ग्राफ़ नहीं हैं। सबसे प्रसिद्ध उदाहरण पीटरसन ग्राफ है, किंतु अन्य का निर्माण किया जा सकता है जिसमें विषम शीर्ष डिग्री वाले किनारे-संक्रमणीय गैर-द्विपक्षीय ग्राफ़ के लाइन ग्राफ़ सम्मिलित हैं।<ref>{{citation | |||
| last1 = Lauri | first1 = Josef | | last1 = Lauri | first1 = Josef | ||
| last2 = Scapellato | first2 = Raffaele | | last2 = Scapellato | first2 = Raffaele | ||
| Line 27: | Line 28: | ||
| volume = 54 | | volume = 54 | ||
| year = 2003}}. Lauri and Scapelleto credit this construction to Mark Watkins.</ref> | | year = 2003}}. Lauri and Scapelleto credit this construction to Mark Watkins.</ref> | ||
== गुण == | == गुण == | ||
कनेक्टिविटी (ग्राफ़ सिद्धांत) | कनेक्टिविटी (ग्राफ़ सिद्धांत) या एक शीर्ष-संक्रमणीय ग्राफ़ की एज -कनेक्टिविटी नियमित ग्राफ़ ''d'' के समान है, जबकि कनेक्टिविटी (ग्राफ़ सिद्धांत) या वर्टेक्स-कनेक्टिविटी कम से कम 2(d + 1)/3 होगी।<ref name=Godsil01/> यदि डिग्री 4 या उससे कम है, या ग्राफ भी किनारे-संक्रमणीय ग्राफ है| जिसके किनारे-संक्रमणीय है, या ग्राफ न्यूनतम केली ग्राफ है, तो शीर्ष-कनेक्टिविटी भी ''d'' के समान होगी।<ref>{{Citation|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago |url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-date=2010-06-11 }}</ref> | ||
== अनंत उदाहरण == | == अनंत उदाहरण == | ||
अनंत शीर्ष-संक्रमणीय ग्राफ़ में | अनंत शीर्ष-संक्रमणीय ग्राफ़ में सम्मिलित हैं: | ||
* अनंत पथ (ग्राफ़ सिद्धांत) (दोनों दिशाओं में अनंत) | * अनंत पथ (ग्राफ़ सिद्धांत) (दोनों दिशाओं में अनंत) | ||
* अनंत नियमित ग्राफ ट्री (ग्राफ सिद्धांत), जैसे। [[मुक्त समूह]] का केली ग्राफ़ | * अनंत नियमित ग्राफ ट्री (ग्राफ सिद्धांत), जैसे। [[मुक्त समूह]] का केली ग्राफ़ | ||
* समान टाइलिंग के ग्राफ़ (प्लानर [[चौकोर]] की एकसमान समतलीय टाइलिंग की सूची देखें), जिसमें नियमित बहुभुजों द्वारा सभी टाइलिंग | * समान टाइलिंग के ग्राफ़ (प्लानर [[चौकोर|टेस्सेलेशन]] की एकसमान समतलीय टाइलिंग की सूची देखें), जिसमें नियमित बहुभुजों द्वारा सभी टाइलिंग सम्मिलित हैं | ||
* अनंत केली | * अनंत केली ग्राफ | ||
*[[राडो ग्राफ]] | *[[राडो ग्राफ]] | ||
दो गणनीय शीर्ष-संक्रमणीय ग्राफ़ को अर्ध-आइसोमेट्रिक कहा जाता है यदि उनके दूरी कार्यों का अनुपात नीचे और ऊपर से घिरा हुआ है। एक प्रसिद्ध अनुमान में कहा गया है कि प्रत्येक अनंत शीर्ष-संक्रमणीय ग्राफ केली ग्राफ के लिए अर्ध-आइसोमेट्रिक है। 2001 में डिएस्टेल और लीडर द्वारा एक प्रति-उदाहरण प्रस्तावित किया गया था।<ref>{{citation|first1=Reinhard|last1=Diestel|first2=Imre|last2=Leader|authorlink2=Imre Leader|url=http://www.math.uni-hamburg.de/home/diestel/papers/Cayley.pdf|title=A conjecture concerning a limit of non-Cayley graphs|journal=Journal of Algebraic Combinatorics|volume=14|issue=1|year=2001|pages=17–25|doi=10.1023/A:1011257718029|s2cid=10927964|doi-access=free}}.</ref> 2005 में, एस्किन, फिशर और व्हाईट ने प्रतिउदाहरण की पुष्टि की थी।<ref>{{cite arXiv|first1=Alex|last1=Eskin|first2=David|last2=Fisher|first3=Kevin|last3=Whyte|eprint=math.GR/0511647 |title=अर्ध-आइसोमेट्री और हल करने योग्य समूहों की कठोरता|year=2005}}.</ref> | |||
दो | |||
== यह भी देखें == | == यह भी देखें == | ||
* एज-ट्रांसिटिव ग्राफ | * एज-ट्रांसिटिव ग्राफ | ||
Revision as of 12:13, 12 August 2023
| 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 | |
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, एक शीर्ष-संक्रमणीय ग्राफ़ एक ग्राफ़ G है जिसमें, G के किन्हीं दो शीर्षों v1 और v2 को देखते हुए, कुछ स्वचालितता होती है
ऐसा है कि
दूसरे शब्दों में, एक ग्राफ शीर्ष-संक्रमणीय होता है यदि इसका ऑटोमोर्फिज्म समूह इसके शीर्षों पर संक्रमणीय रूप से कार्य करता है।[1] एक ग्राफ शीर्ष-संक्रमणीय है यदि और केवल यदि इसका ग्राफ पूरक है, क्योंकि समूह क्रियाएं समान हैं।
पृथक शीर्षों के बिना प्रत्येक सममित ग्राफ शीर्ष-संक्रमणीय है, और प्रत्येक शीर्ष-संक्रमणीय ग्राफ नियमित है। चूँकि , सभी शीर्ष-संक्रमणीय ग्राफ़ सममित नहीं हैं (उदाहरण के लिए, ट्रंकेटेड टेट्राहेड्रोन के किनारे), और सभी नियमित ग्राफ़ शीर्ष-संक्रमणीय नहीं हैं (उदाहरण के लिए, फ्रुचट ग्राफ और टिट्ज़ का ग्राफ)।
परिमित उदाहरण
काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक केली ग्राफ भी) बनाते हैं जो सममित ग्राफ नहीं है।
परिमित शीर्ष-संक्रमणीय ग्राफ में सममित ग्राफ (जैसे पीटरसन ग्राफ, हेवुड ग्राफ और प्लेटोनिक ठोस के शीर्ष और किनारे) सम्मिलित हैं। परिमित केली ग्राफ (जैसे घन-जुड़े चक्र) भी शीर्ष-संक्रमणीय हैं, जैसे कि आर्किमिडीयन ठोस के शीर्ष और किनारे हैं (चूँकि इनमें से केवल दो सममित हैं)। पोटोक्निक, स्पिगा और वेरेट ने अधिकतम 1280 शीर्षों पर सभी जुड़े हुए घन शीर्ष-संक्रमणीय ग्राफ़ की जनगणना का निर्माण किया है।[2]
चूँकि प्रत्येक केली ग्राफ़ शीर्ष-संक्रमणीय है, अन्य शीर्ष-संक्रमणीय ग्राफ़ उपस्थित हैं जो केली ग्राफ़ नहीं हैं। सबसे प्रसिद्ध उदाहरण पीटरसन ग्राफ है, किंतु अन्य का निर्माण किया जा सकता है जिसमें विषम शीर्ष डिग्री वाले किनारे-संक्रमणीय गैर-द्विपक्षीय ग्राफ़ के लाइन ग्राफ़ सम्मिलित हैं।[3]
गुण
कनेक्टिविटी (ग्राफ़ सिद्धांत) या एक शीर्ष-संक्रमणीय ग्राफ़ की एज -कनेक्टिविटी नियमित ग्राफ़ d के समान है, जबकि कनेक्टिविटी (ग्राफ़ सिद्धांत) या वर्टेक्स-कनेक्टिविटी कम से कम 2(d + 1)/3 होगी।[1] यदि डिग्री 4 या उससे कम है, या ग्राफ भी किनारे-संक्रमणीय ग्राफ है| जिसके किनारे-संक्रमणीय है, या ग्राफ न्यूनतम केली ग्राफ है, तो शीर्ष-कनेक्टिविटी भी d के समान होगी।[4]
अनंत उदाहरण
अनंत शीर्ष-संक्रमणीय ग्राफ़ में सम्मिलित हैं:
- अनंत पथ (ग्राफ़ सिद्धांत) (दोनों दिशाओं में अनंत)
- अनंत नियमित ग्राफ ट्री (ग्राफ सिद्धांत), जैसे। मुक्त समूह का केली ग्राफ़
- समान टाइलिंग के ग्राफ़ (प्लानर टेस्सेलेशन की एकसमान समतलीय टाइलिंग की सूची देखें), जिसमें नियमित बहुभुजों द्वारा सभी टाइलिंग सम्मिलित हैं
- अनंत केली ग्राफ
- राडो ग्राफ
दो गणनीय शीर्ष-संक्रमणीय ग्राफ़ को अर्ध-आइसोमेट्रिक कहा जाता है यदि उनके दूरी कार्यों का अनुपात नीचे और ऊपर से घिरा हुआ है। एक प्रसिद्ध अनुमान में कहा गया है कि प्रत्येक अनंत शीर्ष-संक्रमणीय ग्राफ केली ग्राफ के लिए अर्ध-आइसोमेट्रिक है। 2001 में डिएस्टेल और लीडर द्वारा एक प्रति-उदाहरण प्रस्तावित किया गया था।[5] 2005 में, एस्किन, फिशर और व्हाईट ने प्रतिउदाहरण की पुष्टि की थी।[6]
यह भी देखें
- एज-ट्रांसिटिव ग्राफ
- लोवेज़ अनुमान
- अर्ध-सममितीय ग्राफ
- शून्य-सममितीय ग्राफ
संदर्भ
- ↑ 1.0 1.1 Godsil, Chris; Royle, Gordon (2013) [2001], Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, ISBN 978-1-4613-0163-9.
- ↑ Potočnik P., Spiga P. & Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016/j.jsc.2012.09.002, S2CID 26705221.
- ↑ Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts, vol. 54, Cambridge University Press, p. 44, ISBN 0-521-82151-7, MR 1971819. Lauri and Scapelleto credit this construction to Mark Watkins.
- ↑ Babai, L. (1996), Technical Report TR-94-10, University of Chicago, archived from the original on 2010-06-11
- ↑ Diestel, Reinhard; Leader, Imre (2001), "A conjecture concerning a limit of non-Cayley graphs" (PDF), Journal of Algebraic Combinatorics, 14 (1): 17–25, doi:10.1023/A:1011257718029, S2CID 10927964.
- ↑ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "अर्ध-आइसोमेट्री और हल करने योग्य समूहों की कठोरता". arXiv:math.GR/0511647..
बाहरी संबंध
- Weisstein, Eric W. "Vertex-transitive graph". MathWorld.
- A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
