Loading AI tools
З Вікіпедії, вільної енциклопедії
Граф Хівуда — ненаправлений граф з 14 вершинами і 21 ребром, названий на честь Персі Джона Хівуда.[en][1]
Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
Граф Хівуда | |
---|---|
Названо на честь | Персі Джон Хівуд |
Вершин | 14 |
Ребер | 21 |
Радіус | 3 |
Діаметр | 3 |
Обхват | 6 |
Автоморфізм | 336 (PGL2(7)) |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
Спектр | |
Число черг | 2 |
Властивості | Двочастковий Кубічний дистанційно-транзитивний дистанційно-регулярний тороїдальний гамільтонів Симетричний |
Граф є кубічним і всі цикли в графі містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є (3,6)-кліткою, найменшим кубічним графом з обхватом 6. Він є також дистанційно-транзитивним (дивіться список Фостера), а тому дистанційно-регулярним.[2] У графі Хівуда мається 24 паросполучення, і у всіх паросполучень ребра, що не входять у паросполучення, утворюють гамільтонів цикл. Наприклад, малюнок показує вершини графу, поміщені на окружність і що утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами.[2] Зважаючи симетрії графу будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше.[3]
У графі Хівуда 28 циклів, що містять по шість вершин. Кожен такий цикл не пов'язаний в точності з трьома іншими 6-вершинними циклами. Серед цих трьох циклів кожен є симетричною різницею двох інших. Граф в якому кожна вершина відповідає циклу з 6 вершин графу Хівуда, а дуги відповідають незв'язним парам — це граф Коксетера.[4]
Граф Хівуда є тороїдальним графом, тобто його можна відобразити без перетинів на поверхні тора. Як результат утворюється регулярна карта {6,3}2,1 з 7 гексагональними поверхнями. Кожна поверхня мапи суміжна до кожної іншої, а отже карта потребує 7 кольорів. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що не існує карти для тора яка потребує більше 7, а отже карта є максимальною.[5][6]
Ця карта також може бути вірно реалізована як многогранник Сілашші, єдиний відомий полігон, окрім тетраедра, в якому кожна пара граней сусідні.
Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано, тобто графом, представленим інцидентність точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано. Граф Хівуда має число схрещень рівне 3 і є найменшим кубічним графом з таким числом схрещень[7]. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещень 3. Граф Хівуда є графом одиничних відстаней — його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу.[8]
Група автоморфізмів графу Хівуда ізоморфна проективної лінійної групою PGL22(7), групі порядку 336.[9] Він діє транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є симетричним. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі списком Фостера граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами.[10][11] Характеристичний многочлен матриці графу Хівуда — . Спектр графу дорівнює . Це єдиний граф з таким многочленом, який визначається спектром.
Хроматичний многочлен графу дорівнює:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.