Цю статтю треба для відповідності Вікіпедії. (вересень 2015) |
Ця стаття потребує додаткових для поліпшення її . (вересень 2015) |
У теорії графів гра́фом Ме́біуса — Ка́нтора називається симетричний двочастковий кубічний граф з 16 вершинами і 24 ребрами, названий на честь Августа Фердинанда Мебіуса і Зелігмана Кантора (1857—1903). Його можна визначити як узагальнений граф Петерсена G(8,3). Тобто, він утворений вершинами восьмикутника, з'єднаними з восьмикутною зіркою, в якій кожна точка з'єднана з третьої за рахунком точкою.
Граф Мебіуса — Кантора | |
---|---|
Названо на честь | Август Фердинанд Мебіус і Зелігман Кантор |
(Вершин) | 16 |
(Ребер) | 24 |
(Радіус) | 4 |
(Діаметр) | 4 |
(Обхват) | 6 |
(Автоморфізм) | 96 |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
(Рід) | 1 |
Число черг | 2 |
Властивості | Симетричний Гамільтонів Двочастковий Кубічний Граф одиничних відстаней Граф Келі Досконалий |
Конфігурація Мебіуса — Кантора
Мебіус (Möbius 1828) поставив запитання, чи існує пара багатокутників з p сторонами в кожному, які володіють властивістю, що вершини одного багатокутника лежать на прямих, що проходять через сторони іншого, і навпаки. Якщо так, вершини і сторони цих багатокутників повинні утворювати проєктивну конфігурацію. Для p = 4 не існує рішення на евклідовій площині, але Кантор знайшов пару багатокутників такого типу в узагальненні завдання, в якому точки і ребра належать Комплексній проективній площині. Тобто, у рішенні Кантора координатами вершин багатокутника є комплексні числа. Рішення Кантора для p = 4 — пара взаємно вписаних чотирикутника на комплексній проективної площини, називається конфігура́цією Ме́біуса — Ка́нтора. Граф Мебіуса — Кантора отримав своє ім'я від конфігурації Мебіуса — Кантора, оскільки він є графом Леві цій конфігурації. Граф має одну вершину для кожної точки конфігурації і по точці для кожної трійки, а ребра з'єднують дві вершини, якщо одна вершина відповідає точці, а інша трійці, що містить цю точку.
Зв'язок з гіперкубом
Граф Мебіуса — Кантора є підграфом чотиривимірного графу гіперкуба і утворений шляхом видалення восьми ребер з гіперкуба. Оскільки гіперкуб є графом одиничних відстаней, граф Мебіуса — Кантора можна теж намалювати на площині з усіма сторонами одиничної довжини, хоча таке подання призведе до появи перехресних ребер.
Топологія
Граф Мебіуса — Кантора не можна вкласти в площину без перетинів, його число схрещень дорівнює 4, і він є найменшим кубічним графом з таким числом схрещень (послідовність A110507 в OEIS). Крім того, граф дає приклад графу, усі підграфи якого мають кількість перетинів на два і більше від кількості перетинів самого графу. Однак він є тороїдальним — існує його вкладення в тор, при якому всі його грані є шестикутниками. Двоїстий граф цього вкладення — це граф гіпероктаедра K2,2,2,2.
Існує навіть більш симетричне вкладення графу Мебіуса — Кантора в [en], що є регулярним відображенням і має шестеро восьмикутних граней, в якому всі 96 симетрій графу можна здійснити як симетрії вкладення. Коксетер приписує це вкладення Трелфалу. 96-елемантну групу симетрії вкладення має граф Келі, який може бути вкладений в подвійній тор. Такер показав, що це єдина група роду два. Скульптура Де Вітта Годфрея (DeWitt Godfrey) і Дуейн Мартинця (Duane Martinez) у вигляді подвійного тора з вкладеним графом Мебіуса — Кантора була представлена в Технічному музеї Словенії на шостій Словенської Міжнародній конференції з теорії графів в 2007. У 2013 обертаюча версія скульптури була представлена в Колгейтском університеті.
Граф Мебіуса — Кантора допускає вкладення в [en] (тор третього роду), яке дає [en], що має чотири 12-кутні грані.
Лижнен і Кулеманс, досліджуючи можливі хімічні вуглецеві структури, вивчили родину усіх вкладень графу Мебіуса — Кантора в двовимірні многовиди. Вони показали, що існує 759 нееквівалентних вкладень.
Алгебраїчні властивості
- Група автоморфізмів графу Мебіуса — Кантора — це група порядку 96. Вона діє транзитивно на вершини та на ребра, тому Граф Мебіуса — Кантора є симетричним.
- У нього є автоморфізми, які переводять будь-яку вершину в будь-яку іншу і будь-яке ребро в будь-яке інше.
- Згідно зі списком Фостера граф Мебіуса — Кантора є єдиним симетричним графом з 16 вершинами і найменшим кубічним симетричним графом, який не є дистанційно-транзитивним.
- Граф Мебіуса — Кантора є графом Келі.
Узагальнений граф Петерсена G (n, k) є вершинно-транзитивним в тому і тільки в тому випадку, коли n = 10 і k = 2 або коли k² ≡ ± 1 (mod n), і реберно-транзитивним тільки в наступних семи випадках: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), або (24,5) (Frucht, Graver, Watkins, 1971). Таким чином, граф Мебіуса — Кантора є одним з цих семи. Його симетричне вкладення в подвійній тор — одна з семи правильних кубічних карт, для яких загальне число вершин вдвічі більше числа вершин граней. Серед семи симетричних узагальнених графів Петерсена знаходиться кубічний граф G (4,1), граф Петерсена G (5,2), граф додекаедра G (10,2), граф Дезарга G (10,3) і граф Науру G (12,5).
Характерний многочлен графу Мебіуса — Кантора дорівнює
Примітки
- Coxeter, 1950
- Dan McQuillan, R. Bruce Richter On the crossing numbers of certain generalized Petersen graphs // Discrete Mathematics. — 1992. — Т. 104, вып. 3. — С. 311—320.
- Coxeter, 1950.
- Threlfall, 1932.
- Tucker, 1984.
- Marušič, Pisanski, 2000
- Lijnen та Ceulemans, 2004.
- Royle, G. F016A data
- Conder, M.[en], Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- McMullen, 1992
Джерела
- Coxeter, H. S. M. (1950), Self-dual configurations and regular graphs, Bulletin of the American Mathematical Society, 56 (5): 413—455, doi:10.1090/S0002-9904-1950-09407-5 (англ.)
- Lijnen, E.; Ceulemans, A. (2004), Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph, J. Chem. Inf. Comput. Sci., 44 (5): 1552—1564, doi:10.1021/ci049865c, PMID 15446812 (англ.)
- (1984), There is only one group of genus two, Journal of Combinatorial Theory, Series B, 36 (3): 269—275, doi:10.1016/0095-8956(84)90032-7 (англ.)
- Threlfall, W. (1932), Gruppenbilder, Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften, 41 (6): 1—59 (нім.)
Посилання
- Weisstein, Eric W. Möbius-Kantor Graph(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Möbius-Kantor Configuration(англ.) на сайті Wolfram MathWorld.
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti veresen 2015 Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno veresen 2015 U teoriyi grafiv gra fom Me biusa Ka ntora nazivayetsya simetrichnij dvochastkovij kubichnij graf z 16 vershinami i 24 rebrami nazvanij na chest Avgusta Ferdinanda Mebiusa i Zeligmana Kantora 1857 1903 Jogo mozhna viznachiti yak uzagalnenij graf Petersena G 8 3 Tobto vin utvorenij vershinami vosmikutnika z yednanimi z vosmikutnoyu zirkoyu v yakij kozhna tochka z yednana z tretoyi za rahunkom tochkoyu Graf Mebiusa KantoraNazvano na chest Avgust Ferdinand Mebius i Zeligman KantorVershin 16Reber 24Radius 4Diametr 4Obhvat 6Avtomorfizm 96Hromatichne chislo 2Hromatichnij indeks 3Rid 1Chislo cherg 2Vlastivosti Simetrichnij Gamiltoniv Dvochastkovij Kubichnij Graf odinichnih vidstanej Graf Keli DoskonalijKonfiguraciya Mebiusa KantoraDokladnishe Konfiguraciya Mebiusa Kantora Konfiguraciya Mebiusa Kantora Mebius Mobius 1828 postaviv zapitannya chi isnuye para bagatokutnikiv z p storonami v kozhnomu yaki volodiyut vlastivistyu sho vershini odnogo bagatokutnika lezhat na pryamih sho prohodyat cherez storoni inshogo i navpaki Yaksho tak vershini i storoni cih bagatokutnikiv povinni utvoryuvati proyektivnu konfiguraciyu Dlya p 4 ne isnuye rishennya na evklidovij ploshini ale Kantor znajshov paru bagatokutnikiv takogo tipu v uzagalnenni zavdannya v yakomu tochki i rebra nalezhat Kompleksnij proektivnij ploshini Tobto u rishenni Kantora koordinatami vershin bagatokutnika ye kompleksni chisla Rishennya Kantora dlya p 4 para vzayemno vpisanih chotirikutnika na kompleksnij proektivnoyi ploshini nazivayetsya konfigura ciyeyu Me biusa Ka ntora Graf Mebiusa Kantora otrimav svoye im ya vid konfiguraciyi Mebiusa Kantora oskilki vin ye grafom Levi cij konfiguraciyi Graf maye odnu vershinu dlya kozhnoyi tochki konfiguraciyi i po tochci dlya kozhnoyi trijki a rebra z yednuyut dvi vershini yaksho odna vershina vidpovidaye tochci a insha trijci sho mistit cyu tochku Zv yazok z giperkubomGraf Mebiusa Kantora ye pidgrafom chotirivimirnogo grafu giperkuba i utvorenij shlyahom vidalennya vosmi reber z giperkuba Oskilki giperkub ye grafom odinichnih vidstanej graf Mebiusa Kantora mozhna tezh namalyuvati na ploshini z usima storonami odinichnoyi dovzhini hocha take podannya prizvede do poyavi perehresnih reber TopologiyaUzagalnenij graf Mebiusa Kantora vkladenij v tor Rebra sho vihodyat vgoru z centralnogo kvadrata slid rozglyadati z yednanimi z vidpovidnimi rebrami sho vihodyat z kvadrata vniz a vihodyat z kvadrata rebra zliva slid rozglyadati z yednanimi z vidpovidnimi rebrami sho vihodyat z kvadrata vpravo Graf Mebiusa Kantora ne mozhna vklasti v ploshinu bez peretiniv jogo chislo shreshen dorivnyuye 4 i vin ye najmenshim kubichnim grafom z takim chislom shreshen poslidovnist A110507 v OEIS Krim togo graf daye priklad grafu usi pidgrafi yakogo mayut kilkist peretiniv na dva i bilshe vid kilkosti peretiniv samogo grafu Odnak vin ye toroyidalnim isnuye jogo vkladennya v tor pri yakomu vsi jogo grani ye shestikutnikami Dvoyistij graf cogo vkladennya ce graf giperoktaedra K2 2 2 2 Isnuye navit bilsh simetrichne vkladennya grafu Mebiusa Kantora v en sho ye regulyarnim vidobrazhennyam i maye shestero vosmikutnih granej v yakomu vsi 96 simetrij grafu mozhna zdijsniti yak simetriyi vkladennya Kokseter pripisuye ce vkladennya Trelfalu 96 elemantnu grupu simetriyi vkladennya maye graf Keli yakij mozhe buti vkladenij v podvijnij tor Taker pokazav sho ce yedina grupa rodu dva Skulptura De Vitta Godfreya DeWitt Godfrey i Duejn Martincya Duane Martinez u viglyadi podvijnogo tora z vkladenim grafom Mebiusa Kantora bula predstavlena v Tehnichnomu muzeyi Sloveniyi na shostij Slovenskoyi Mizhnarodnij konferenciyi z teoriyi grafiv v 2007 U 2013 obertayucha versiya skulpturi bula predstavlena v Kolgejtskom universiteti Graf Mebiusa Kantora dopuskaye vkladennya v en tor tretogo rodu yake daye en sho maye chotiri 12 kutni grani Lizhnen i Kulemans doslidzhuyuchi mozhlivi himichni vuglecevi strukturi vivchili rodinu usih vkladen grafu Mebiusa Kantora v dvovimirni mnogovidi Voni pokazali sho isnuye 759 neekvivalentnih vkladen Algebrayichni vlastivostiGrupa avtomorfizmiv grafu Mebiusa Kantora ce grupa poryadku 96 Vona diye tranzitivno na vershini ta na rebra tomu Graf Mebiusa Kantora ye simetrichnim U nogo ye avtomorfizmi yaki perevodyat bud yaku vershinu v bud yaku inshu i bud yake rebro v bud yake inshe Zgidno zi spiskom Fostera graf Mebiusa Kantora ye yedinim simetrichnim grafom z 16 vershinami i najmenshim kubichnim simetrichnim grafom yakij ne ye distancijno tranzitivnim Graf Mebiusa Kantora ye grafom Keli Uzagalnenij graf Petersena G n k ye vershinno tranzitivnim v tomu i tilki v tomu vipadku koli n 10 i k 2 abo koli k 1 mod n i reberno tranzitivnim tilki v nastupnih semi vipadkah n k 4 1 5 2 8 3 10 2 10 3 12 5 abo 24 5 Frucht Graver Watkins 1971 Takim chinom graf Mebiusa Kantora ye odnim z cih semi Jogo simetrichne vkladennya v podvijnij tor odna z semi pravilnih kubichnih kart dlya yakih zagalne chislo vershin vdvichi bilshe chisla vershin granej Sered semi simetrichnih uzagalnenih grafiv Petersena znahoditsya kubichnij graf G 4 1 graf Petersena G 5 2 graf dodekaedra G 10 2 graf Dezarga G 10 3 i graf Nauru G 12 5 Harakternij mnogochlen grafu Mebiusa Kantora dorivnyuye x 3 x 1 3 x 1 3 x 3 x 2 3 4 displaystyle x 3 x 1 3 x 1 3 x 3 x 2 3 4 PrimitkiCoxeter 1950 Dan McQuillan R Bruce Richter On the crossing numbers of certain generalized Petersen graphs Discrete Mathematics 1992 T 104 vyp 3 S 311 320 Coxeter 1950 Threlfall 1932 Tucker 1984 Marusic Pisanski 2000 Lijnen ta Ceulemans 2004 Royle G F016A data Conder M en Dobcsanyi P Trivalent Symmetric Graphs Up to 768 Vertices J Combin Math Combin Comput 40 41 63 2002 McMullen 1992DzherelaCoxeter H S M 1950 Self dual configurations and regular graphs Bulletin of the American Mathematical Society 56 5 413 455 doi 10 1090 S0002 9904 1950 09407 5 angl Lijnen E Ceulemans A 2004 Oriented 2 Cell Embeddings of a Graph and Their Symmetry Classification Generating Algorithms and Case Study of the Mobius Kantor Graph J Chem Inf Comput Sci 44 5 1552 1564 doi 10 1021 ci049865c PMID 15446812 angl 1984 There is only one group of genus two Journal of Combinatorial Theory Series B 36 3 269 275 doi 10 1016 0095 8956 84 90032 7 angl Threlfall W 1932 Gruppenbilder Abhandlungen der Mathematisch Physischen Klasse der Sachsischen Akademie der Wissenschaften 41 6 1 59 nim PosilannyaWeisstein Eric W Mobius Kantor Graph angl na sajti Wolfram MathWorld Weisstein Eric W Mobius Kantor Configuration angl na sajti Wolfram MathWorld Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi