Алмаз (теорія графів)

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

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

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

Графи без алмазів і заборонені мінори

Граф є вільним від алмазів, якщо він не містить алмаза в якості породженого підграфа. Графи без трикутників є вільними від алмазів, оскільки будь-який алмаз містить трикутник.

Сімейство графів, в якому кожна зв'язна компонента є кактусом, замкнуто донизу відносно операції утворення мінору графа. Це сімейство графів може бути описано єдиним забороненим мінором — алмазом^[4].

Якщо метелик й алмаз є забороненими мінорами, отримане сімейство графів є сімейством псевдолісів.

Алгебраїчні властивості

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

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