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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга