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

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

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

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

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

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

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

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

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

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

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

Литература

• 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.