Бабочка (теория графов)

Граф «Бабочка»

Вершин	5
Рёбер	6
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	8 (D₄)
Хроматическое число	3
Хроматический индекс	4
Свойства	планарный граф единичных расстояний эйлеров не имеют грациозной разметки
Медиафайлы на Викискладе

В теории графов граф «бабочка» (а также «галстук-бабочка» или «песочные часы») — это планарный неориентированный граф с 5 вершинами и 6 рёбрами^[1]^[2]. Граф может быть построен объединением двух копий циклов C₃ по одной общей вершине, а потому граф изоморфен графу дружеских отношений F₂.

Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.

Существует только 3 не имеющих грациозной разметки простых графов с пятью вершинами. Один из них — бабочка. Два других — цикл C₅ и полный граф K₅^[3].

Графы, не содержащие бабочек

Граф является свободным от бабочек, если он не имеет бабочку в качестве порождённого подграфа. Графы без треугольников являются графами без бабочек, поскольку граф-бабочка содержит треугольники.

В вершинно k-связном графе ребро называется k-стягивающим, если стягивание ребра приводит к k-связному графу. Андо, Канеко, Каварабайаши и Йошимото доказали, что любой вершинно k-связный граф без бабочек имеет k-стягиваемое ребро^[4].

Алгебраические свойства

Полная группа автоморфизмов графа-бабочки является группой порядка 8, изоморфной D₄, группе симметрии квадрата, включая вращение и отражений.

Характеристическим многочленом матрицы графа-бабочки является $-(x-1)(x+1)^{2}(x^{2}-x-4)$ .

Примечания

↑ Weisstein, Eric W. Butterfly Graph (англ.) на сайте Wolfram MathWorld.
↑ ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs Архивная копия от 22 июля 2012 на Wayback Machine".
↑ Weisstein, Eric W. Graceful graph (англ.) на сайте Wolfram MathWorld.
↑ Ando, 2007, с. 10–20.

Литература

Kiyoshi Ando. Discrete geometry, combinatorics and graph theory. — Springer, Berlin, 2007. — Т. 4381. — С. 10–20. — (Lecture Notes in Comput. Sci.). — doi:10.1007/978-3-540-70666-3_2.

Похожие исследовательские статьи

<span class="mw-page-title-main">Граф Грёча</span> граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5

Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.

В теории графов треугольным графом называется планарный неориентированный граф с тремя вершинами и тремя рёбрами, образующими треугольник.

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .

Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

Граф Татта — пример кубического полиэдрального графа, не являющегося гамильтоновым. Таким образом, он служит контрпримером к гипотезе Тэйта, предполагавшей, что любой 3-регулярный многогранник имеет гамильтонов цикл.

В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

В теории графов лестница L_n — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.

Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами. Граф представляет собой полный граф $\text{[math]}$ без одного ребра.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Бидиакис-куб — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.