| График бабочки | |
|---|---|
 | |
| Вершины | 5 |
| Края | 6 |
| Радиус | 1 |
| Диаметр | 2 |
| Обхват | 3 |
| Автоморфизмы | 8 ( D 4 ) |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Характеристики | Планарное Единичное расстояние Эйлерово Не изящное |
| Таблица графиков и параметров | |
В математической области теории графов , то бабочки графа (также называемый Боути график и песочные график ) является плоской неориентированный граф с 5 вершинами и 6 ребрами. [1] [2] Он может быть построен путем соединения 2 копий графа циклов C 3 с общей вершиной и, следовательно, изоморфен графу дружбы F 2 .
График бабочки имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и одновременно эйлеров и пенни граф (это означает, что это единичное расстояние и планарен ). Это также граф с одной вершиной и граф с двумя ребрами .
Есть только 3 не изящных простых графа с пятью вершинами. Один из них - график-бабочка. Два других - это граф циклов C 5 и полный граф K 5 . [3]
Графики без бабочек [ править ]
Граф свободен от бабочки, если в нем нет индуцированного подграфа бабочки . В треугольнике свободной графики являются Bowtie свободных графов, поскольку каждая бабочка содержит треугольник.
В графе, связанном с k- вершинами , ребро называется k - стягиваемым, если сжатие ребра приводит к k -связному графу. Андо, Канеко, Каварабаяси и Йошимото доказали, что каждый граф без галстука-бабочки с k- вершинами имеет k -сжимаемое ребро. [4]
Алгебраические свойства [ править ]
Полная группа автоморфизмов графа-бабочки - это группа порядка 8, изоморфная группе диэдра D 4 , группе симметрий квадрата , включая как вращения, так и отражения.
Характеристический полином бабочки графа .
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. "График бабочки" . MathWorld .
- ^ ISGCI: Информационная система по классам графов и их включениям. « Список малых графов ».
- ^ Вайсштейн, Эрик В. "Изящный граф" . MathWorld .
- ↑ Андо, Киёси (2007), «Сжимаемые ребра в k -связном графе», Дискретная геометрия, комбинаторика и теория графов , Конспект лекций по вычислениям. Sci . , 4381 ., Springer, Berlin, стр 10-20, DOI : 10.1007 / 978-3-540-70666-3_2 , МР 2364744 .
