Граф Дюрера
Граф Дюрера — неорієнтований кубічний граф з 12 вершинами і 18 ребрами. Граф названо ім'ям Альбрехта Дюрера, чия гравюра «Меланхолія» (1514) містила зображення так званого багатогранника Дюрера — опуклого багатогранника, кістяком якого є граф Дюрера. Багатогранник Дюрера є одним з чотирьох можливих добре покритих простих опуклих багатогранників.
Багатогранник Дюрера
Шаблон:Докладніше Багатогранник Дюрера комбінаторно еквівалентний кубу з двома зрізаними протилежними вершинами, хоча на малюнку Дюрера він, швидше, зображений як зрізаний ромбоедр або тригранний зрізаний трапецоїдШаблон:Sfn. Точні геометричні властивості намальованого Дюрером багатогранника є предметом академічних суперечок, у яких припускаються різні гіпотетичні значення (гострих) кутів від 72° до 82°Шаблон:Sfn.
Властивості графу
Граф Дюрера — це граф, утворений вершинами і ребрами багатогранника Дюрера. Граф є кубічним з обхватом 3 і діаметром 4. Оскільки граф є кістяком багатогранника Дюрера, його можна отримати, застосувавши перетворення трикутник-зірка протилежних вершин графу куба, або як узагальнений граф Петерсена . Як і будь-який інший граф опуклого багатогранника, граф Дюрера є вершинно 3-зв'язним простим планарним графом.
Граф Дюрера є добре покритим, що означає, що всі його найбільші незалежні множини мають однакове число вершин — чотири. Граф є одним з добре покритих кубічних багатогранних графів і одним з семи добре покритих 3-зв'язних кубічних графів. Іншими трьома добре покритими простими опуклими багатогранниками є тетраедр, трикутна призма і п'ятикутна призмаШаблон:SfnШаблон:Sfn.
Граф Дюрера є гамільтоновим з LCF-позначенням [-4,5,2,-4,-2,5;-][1]. Точніше, граф має рівно шість гамільтонових циклів, кожну пару яких можна відобразити в будь-яку іншу симетріями графуШаблон:Sfnp.
Симетрії
Група автоморфізмів як графу Дюрера, так і багатогранника Дюрера (у вигляді зрізаного куба або у формі, наведеній Дюрером) ізоморфна діедральній групі порядку 12.
Галерея
-
Хроматичний індекс графу Дюрера дорівнює 3. -
Хроматичне число графу Дюрера дорівнює 3. -
Граф Дюрера гамільтонів.
Примітки
Література
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття (як процитовано у Вайцеля (Шаблон:Harvtxt).
- Шаблон:Стаття
- ↑ Кастанья і Прінс (Шаблон:Harvtxt) приписують доведення гамільтоновості класу узагальнених графів Петерсена, до якого належить граф Дюрера, тезам дисертації 1968 року Робертсона (G. N. Robertson) з університету Ватерлоо.