Метелик (теорія графів)

Шаблон:Граф У теорії графів граф «метелик» (а також «краватка-метелик» або «пісковий годинник») — це планарний неорієнтований граф з 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)$.

Див. також

• Голова бика (теорія графів)

Література

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