Русская Википедия:Граф Дюрера
Граф Дюрера — неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Альбрехта Дюрера, чья гравюра «Меланхолия» (1514) содержала изображение так называемого многогранника Дюрера — выпуклого многогранника, имеющего граф Дюрера в качестве Шаблон:Не переведено 5. Многогранник Дюрера является одним из четырёх возможных хорошо укрытых простых выпуклых многогранников.
Многогранник Дюрера
Шаблон:Main Многогранник Дюрера комбинаторно эквивалентен кубу с двумя усечёнными противоположными вершинами[1], хотя на рисунке Дюрера он, скорее, нарисован как усечённый ромбоэдр или трёхгранный усечённый трапецоидШаблон:Sfn. Точные геометрические свойства нарисованного Дюрером многогранника служат предметом академических споров, в которых предполагаются различные гипотетические значения (острых) углов от 72° до 82°Шаблон:Sfn.
Свойства графа
Шаблон:Граф Граф Дюрера является графом, образованным вершинами и рёбрами многогранника Дюрера. Граф является кубическим с обхватом 3 и диаметром 4. Поскольку граф является скелетом многогранника Дюрера, он может быть получен путём применения преобразования треугольник-звезда противоположных вершин графа куба или как обобщённый граф Петерсена <math>G(6,2)</math>. Как и любой другой граф выпуклого многогранника, граф Дюрера является вершинно 3-связным простым планарным графом.
Граф Дюрера является хорошо укрытым, что означает, что все его наибольшие независимые множества имеют одно и то же число вершин — четыре. Граф является одним из хорошо укрытых кубических многогранных графов и одним из семи хорошо укрытых 3-связных кубических графов. Другими тремя хорошо укрытыми простыми выпуклыми многогранниками являются тетраэдр, треугольная призма и пятиугольная призмаШаблон:SfnШаблон:Sfn.
Граф Дюрера является гамильтоновым с LCF-обозначением [-4,5,2,-4,-2,5;-][2]. Точнее, граф имеет ровно шесть гамильтоновых циклов, каждая пара которых может быть отображена в любую другую симметриями графаШаблон:Sfnp.
Симметрии
Группа автоморфизмов как графа Дюрера, так и многогранника Дюрера (в виде усечённого куба или в форме, представленной Дюрером) изоморфна диэдрической группе <math>D_6</math> порядка 12.
Галерея
-
Хроматический индекс графа Дюрера равен 3.
-
Хроматическое число графа Дюрера равно 3.
-
Граф Дюрера гамильтонов.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья (как процитировано у Вайцеля (Шаблон:Harvtxt).
- Шаблон:Статья
- ↑ Шаблон:MathWorld
- ↑ Кастанья и Принс (Шаблон:Harvtxt) приписывают доказательство гамильтоновости класса обобщённых графов Петерсона, в который входит граф Дюрера, тезисам диссертации 1968 года Робертсона (G. N. Robertson) из университета Ватерлоо.
