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

Граф «Бабочка»
Вершин	5
Рёбер	6
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	8 (D4)
Хроматическое число	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₄, группе симметрии квадрата, включая вращение и отражений.

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

Примечания

1. Weisstein, Eric W. Butterfly Graph (англ.) на сайте Wolfram MathWorld.
2. ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs Архивная копия от 22 июля 2012 на Wayback Machine".
3. Weisstein, Eric W. Graceful graph (англ.) на сайте Wolfram MathWorld.
4. 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.