Бабочка (теория графов)
В теории графов граф «бабочка» (а также «галстук-бабочка» или «песочные часы») — это планарный неориентированный граф с 5 вершинами и 6 рёбрами[1][2]. Граф может быть построен объединением двух копий циклов C3 по одной общей вершине, а потому граф изоморфен графу дружеских отношений F2.
| Граф «Бабочка» | |
|---|---|
 | |
| Вершин | 5 |
| Рёбер | 6 |
| Радиус | 1 |
| Диаметр | 2 |
| Обхват | 3 |
| Автоморфизмы | 8 (D4) |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Свойства |
планарный граф единичных расстояний эйлеров не имеют грациозной разметки |
 Медиафайлы на Викискладе | |
Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.
Существует только 3 не имеющих грациозной разметки простых графов с пятью вершинами. Один из них — бабочка. Два других — цикл C5 и полный граф K5[3].
Графы, не содержащие бабочек
Граф является свободным от бабочек, если он не имеет бабочку в качестве порождённого подграфа. Графы без треугольников являются графами без бабочек, поскольку граф-бабочка содержит треугольники.
В вершинно k-связном графе ребро называется k-стягивающим, если стягивание ребра приводит к k-связному графу. Андо, Канеко, Каварабайаши и Йошимото доказали, что любой вершинно k-связный граф без бабочек имеет k-стягиваемое ребро[4].
Алгебраические свойства
Полная группа автоморфизмов графа-бабочки является группой порядка 8, изоморфной D4, группе симметрии квадрата, включая вращение и отражений.
Характеристическим многочленом матрицы графа-бабочки является .
Примечания
- Weisstein, Eric W. Butterfly Graph (англ.) на сайте Wolfram MathWorld.
- ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".
- 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.