WikiSort.ru - Не сортированное

Алмаз
Вершин	4
Рёбер	5
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	4 (Z/2Z×Z/2Z)
Хроматическое число	3
Хроматический индекс	3
Свойства	Граф единичных расстояний планарный Гамильтонов

Алмаз — это планарный неориентированный граф с 4 вершинами и 5 рёбрами^[1][2]. Граф представляет собой полный граф ${\displaystyle K_{4}}$ без одного ребра.

Радиус алмаза равен 1, диаметр равен 2, обхват равен 3, хроматический индекс и хроматическое число равны 3. Граф также вершинно 2-связен и рёберно 2-связен, имеет грациозную разметку^[3] и является гамильтоновым.

Графы без алмазов и запрещённые миноры

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

Семейство графов, в котором каждая связная компонента является кактусом, замкнуто вниз относительно операции образования минора графа. Это семейство графов может быть описано единственным запрещённым минором — алмазом^[4].

Если бабочка и алмаз являются запрещёнными минорами, полученное семейство графов является семейством псевдолесов.

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

Группа автоморфизмов алмаза является группой порядка 4, изоморфной четверной группе Клейна, прямому произведению циклической группы Z/2Z на себя.

Характеристический многочлен алмаза равен ${\displaystyle x(x+1)(x^{2}-x-4)}$ . Алмаз является единственным графом с характеристическим многочленом, определяющим граф его спектром.

См. также

• Матроид Вамоса^[en]

Примечания

Литература

• 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.