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

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

Характеристичним многочленом матриці графу-метелика є .

Примітки
  1. Weisstein, Eric W. Butterfly Graph(англ.) на сайті Wolfram MathWorld.
  2. ISGCI: Information System on Graph Classes and their Inclusions. «List of Small Graphs».
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.