Алмаз (теория графов)
Алмаз — это планарный неориентированный граф с 4 вершинами и 5 рёбрами[1][2]. Граф представляет собой полный граф без одного ребра.
Радиус алмаза равен 1, диаметр равен 2, обхват равен 3, хроматический индекс и хроматическое число равны 3. Граф также вершинно 2-связен и рёберно 2-связен, имеет грациозную разметку[3] и является гамильтоновым.
Что важно знать
| Алмаз | |
|---|---|
| Вершин | 4 |
| Рёбер | 5 |
| Радиус | 1 |
| Диаметр | 2 |
| Обхват | 3 |
| Автоморфизмы | 4 (Z/2Z×Z/2Z) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Свойства |
Граф единичных расстояний планарный Гамильтонов |
Графы без алмазов и запрещённые миноры
Граф является свободным от алмазов, если он не содержит алмаза в качестве порождённого подграфа. Графы без треугольников являются свободными от алмазов, поскольку любой алмаз содержит треугольник.
Семейство графов, в котором каждая связная компонента является кактусом, замкнуто вниз относительно операции образования минора графа. Это семейство графов может быть описано единственным запрещённым минором — алмазом[4].
Если бабочка и алмаз являются запрещёнными минорами, полученное семейство графов является семейством псевдолесов.
Алгебраические свойства
Группа автоморфизмов алмаза является группой порядка 4, изоморфной четверной группе Клейна, прямому произведению циклической группы Z/2Z на себя.
Характеристический многочлен алмаза равен . Алмаз является единственным графом с характеристическим многочленом, определяющим граф его спектром.
См. также
Примечания
Литература
- Ehab El-Mallah, Charles J. Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вып. 3. — С. 354–362. — doi:10.1109/31.1748.
