Перегляд вихідного коду сторінки Граф Мебіуса — Кантора

{{Вікіфікувати|дата=вересень 2015}}
{{Refimprove|дата=вересень 2015}}

{{Граф
 | name = Граф Мебіуса — Кантора
 | image = [[Файл:Möbius–Kantor unit distance.svg|frameless|upright=1]]
 | namesake = [[Август Фердинанд Мебіус]] і Зелігман Кантор
 | vertices = 16
 | edges = 24
 | girth = 6
 | radius = 4
 | diameter = 4
 | automorphisms = 96
 | chromatic_number = 2
 | chromatic_index = 3
 | genus = 1
 | queue_number = 2
 | properties = [[Симетричний граф|Симетричний]]<br>[[Гамільтонів граф|Гамільтонів]]<br>[[Двочастковий граф|Двочастковий]]<br>[[Кубічний граф|Кубічний]]<br>[[Граф одиничних відстаней]]<br/>[[Граф Келі]]<br/>[[Досконалий граф|Досконалий]]
}}
У [[Теорія графів|теорії графів]] '''гра́фом Ме́біуса&nbsp;— Ка́нтора''' називається [[Симетричний граф|симетричний]] [[Двочастковий граф|двочастковий]] [[кубічний граф]] з 16 вершинами і 24 ребрами, названий на честь [[Август Фердинанд Мебіус|Августа Фердинанда Мебіуса]] і Зелігмана Кантора (1857—1903). Його можна визначити як [[узагальнений граф Петерсена]] G(8,3). Тобто, він утворений вершинами [[восьмикутник]]а, з'єднаними з восьмикутною зіркою, в якій кожна точка з'єднана з третьої за рахунком точкою.

== Конфігурація Мебіуса&nbsp;— Кантора ==
{{Докладніше|Конфігурація Мебіуса — Кантора}}
[[Файл:Möbius–Kantor configuration.svg|thumb|left| [[Конфігурація Мебіуса — Кантора]]]]

Мебіус (Möbius 1828) поставив запитання, чи існує пара [[багатокутник]]ів з p сторонами в кожному, які володіють властивістю, що вершини одного багатокутника лежать на прямих, що проходять через сторони іншого, і навпаки. Якщо так, вершини і сторони цих багатокутників повинні утворювати [[Проєктивна конфігурація|проєктивну конфігурацію]]. Для p = 4 не існує рішення на [[Евклідова площина|евклідовій площині]], але Кантор знайшов пару [[багатокутник]]ів такого типу в узагальненні завдання, в якому точки і ребра належать [[Комплексна проєктивна площина|Комплексній проективній площині]]. Тобто, у рішенні Кантора координатами вершин багатокутника є [[комплексні числа]]. Рішення Кантора для p = 4&nbsp;— пара взаємно вписаних чотирикутника на комплексній проективної площини, називається '''конфігура́цією Ме́біуса&nbsp;— Ка́нтора'''. Граф Мебіуса&nbsp;— Кантора отримав своє ім'я від конфігурації Мебіуса&nbsp;— Кантора, оскільки він є [[Граф Леві|графом Леві]] цій конфігурації. Граф має одну вершину для кожної точки конфігурації і по точці для кожної трійки, а ребра з'єднують дві вершини, якщо одна вершина відповідає точці, а інша трійці, що містить цю точку.

== Зв'язок з гіперкубом ==
Граф Мебіуса&nbsp;— Кантора є підграфом чотиривимірного [[Граф гіперкуба|графу гіперкуба]] і утворений шляхом видалення восьми ребер з гіперкуба<ref>Coxeter, 1950</ref>. Оскільки гіперкуб є графом одиничних відстаней, граф Мебіуса&nbsp;— Кантора можна теж намалювати на площині з усіма сторонами одиничної довжини, хоча таке подання призведе до появи перехресних ребер.

== Топологія ==
[[Файл:Möbius–Kantor torus.svg|thumb|upright=1.2|Узагальнений граф Мебіуса&nbsp;— Кантора, вкладений в тор. Ребра, що виходять вгору з центрального квадрата слід розглядати з'єднаними з відповідними ребрами, що виходять з квадрата вниз, а виходять з квадрата ребра зліва слід розглядати з'єднаними з відповідними ребрами, що виходять з квадрата вправо.]]
Граф Мебіуса&nbsp;— Кантора не можна вкласти в площину без перетинів, його [[число схрещень]] дорівнює 4, і він є найменшим кубічним графом з таким числом схрещень (послідовність A110507 в [[OEIS]]). Крім того, граф дає приклад графу, усі підграфи якого мають кількість перетинів на два і більше від кількості перетинів самого графу<ref>Dan McQuillan, R. Bruce Richter On the crossing numbers of certain generalized Petersen graphs // Discrete Mathematics.&nbsp;— 1992.&nbsp;— Т. 104, вып. 3.&nbsp;— С. 311—320.</ref>. Однак він є [[Тороїдальний граф|тороїдальним]]&nbsp;— існує його вкладення в [[Тор (геометрія)|тор]], при якому всі його грані є [[шестикутник]]ами. [[Двоїстий граф]] цього вкладення&nbsp;— це [[Граф Турану|граф гіпероктаедра]] ''K''<sub>2,2,2,2</sub>.

Існує навіть більш симетричне вкладення графу Мебіуса&nbsp;— Кантора в {{Нп|подвійний тор||en|Genus-2 surface}}, що є регулярним відображенням і має шестеро восьмикутних граней, в якому всі 96 симетрій графу можна здійснити як симетрії вкладення. Коксетер{{sfn|Coxeter|1950}} приписує це вкладення Трелфалу.{{sfn|Threlfall|1932}} 96-елемантну групу симетрії вкладення має [[граф Келі]], який може бути вкладений в подвійній тор. Такер{{sfn|Tucker|1984}} показав, що це єдина група роду два. Скульптура Де Вітта Годфрея (DeWitt Godfrey) і Дуейн Мартинця (Duane Martinez) у вигляді подвійного тора з вкладеним графом Мебіуса&nbsp;— Кантора була представлена в Технічному музеї Словенії на шостій Словенської Міжнародній конференції з теорії графів в 2007. У 2013 обертаюча версія скульптури була представлена в Колгейтском університеті.

Граф Мебіуса&nbsp;— Кантора допускає вкладення в {{Нп|потрійний тор|||Triple torus}} (тор третього роду), яке дає {{Нп|Правильна карта (теорія графів)|правильну карту|en|Regular map (graph theory)}}, що має чотири 12-кутні грані<ref> Marušič, Pisanski, 2000</ref>.

Лижнен і Кулеманс,{{sfn|Lijnen|Ceulemans|2004}} досліджуючи можливі хімічні вуглецеві структури, вивчили родину усіх вкладень графу Мебіуса&nbsp;— Кантора в двовимірні многовиди. Вони показали, що існує 759 нееквівалентних вкладень.

== Алгебраїчні властивості ==
* Група автоморфізмів графу Мебіуса&nbsp;— Кантора&nbsp;— це група порядку 96<ref>Royle, G. F016A data</ref>. Вона діє транзитивно на вершини та на ребра, тому Граф Мебіуса&nbsp;— Кантора є симетричним.
* У нього є автоморфізми, які переводять будь-яку вершину в будь-яку іншу і будь-яке ребро в будь-яке інше.
* Згідно зі списком Фостера граф Мебіуса&nbsp;— Кантора є єдиним [[симетричний граф|симетричним графом]] з 16 вершинами і найменшим кубічним симетричним графом, який не є [[Дистанційно-транзитивний граф|дистанційно-транзитивним]]<ref>Conder, M.[en], Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.</ref>.
* Граф Мебіуса&nbsp;— Кантора є [[граф Келі|графом Келі]].

[[Узагальнений граф Петерсена]] 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) {{harv|Frucht, Graver, Watkins|1971}}. Таким чином, граф Мебіуса&nbsp;— Кантора є одним з цих семи. Його симетричне вкладення в подвійній тор&nbsp;— одна з семи правильних кубічних карт, для яких загальне число вершин вдвічі більше числа вершин граней<ref>McMullen, 1992</ref>. Серед семи симетричних узагальнених графів Петерсена знаходиться [[кубічний граф]] G (4,1), [[граф Петерсена]] G (5,2), граф додекаедра G (10,2), [[граф Дезарга]] G (10,3) і [[граф Науру]] G (12,5).

Характерний многочлен графу Мебіуса&nbsp;— Кантора дорівнює

: <math>(x-3)(x-1)^3(x+1)^3(x+3)(x^2-3)^4.\ </math>

== Примітки ==
{{Примітки}}

== Джерела ==

* {{citation
 | authorlink = Гарольд Коксетер
 | first = H. S. M. | last = Coxeter
 | title = Self-dual configurations and regular graphs
 | journal = [[Bulletin of the American Mathematical Society]]
 | volume = 56 | year = 1950 | pages = 413–455
 | doi = 10.1090/S0002-9904-1950-09407-5
 | issue = 5
 | ref = harv
}} {{ref-en}}
* {{citation
 | first1 = E. | last1 = Lijnen
 | first2 = A. | last2 = Ceulemans
 | title = Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph
 | journal = J. Chem. Inf. Comput. Sci.
 | volume = 44
 | issue = 5
 | pages = 1552–1564
 | year = 2004
 | doi = 10.1021/ci049865c
 | pmid = 15446812
 | ref = harv
}} {{ref-en}}
* {{citation
 | last = Tucker | first = Thomas W.
 | authorlink = Томас Такер
 | year = 1984
 | title = There is only one group of genus two
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 36
 | pages = 269–275
 | doi = 10.1016/0095-8956(84)90032-7
 | issue = 3
 | ref = harv
}} {{ref-en}}
* {{citation
 | first = W. | last = Threlfall
 | title = Gruppenbilder
 | journal = Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften
 | volume = 41 | issue = 6 | year = 1932 | pages = 1–59
 | ref = harv
}} {{ref-de}}

== Посилання ==
* {{MathWorld | urlname = Moebius-KantorGraph | title = Möbius-Kantor Graph}}
* {{MathWorld | urlname = Moebius-KantorConfiguration | title = Möbius-Kantor Configuration}}

{{Math-stub}}

[[Категорія:Теорія графів]]
[[Категорія:Регулярні графи]]