Алмаз (теорія графів)
Алмаз — це планарний неорієнтований граф із 4 вершинами та 5 ребрами[1][2]. Граф являє собою повний граф без одного ребра.
Радіус алмаза дорівнює 1, діаметр дорівнює 2, обхват дорівнює 3, хроматичний індекс і хроматичне число дорівнюють 3. Граф також вершинно 2-зв'язаний і реберно 2-зв'язаний, має граціозну розмітку[3] і є гамільтоновим.
Графи без алмазів і заборонені мінори
Граф є вільним від алмазів, якщо він не містить алмаза в якості породженого підграфа. Графи без трикутників є вільними від алмазів, оскільки будь-який алмаз містить трикутник.
Сімейство графів, в якому кожна зв'язна компонента є кактусом, замкнуто донизу відносно операції утворення мінору графа. Це сімейство графів може бути описано єдиним забороненим мінором — алмазомШаблон:Sfn.
Якщо метелик й алмаз є забороненими мінорами, отримане сімейство графів є сімейством псевдолісів.
Алгебраїчні властивості
Група автоморфізмів алмаза є групою порядку 4, ізоморфною четверній групі Клейна, прямому добутку циклічної групи Z/2Z на себе.
Характеристичний многочлен алмаза дорівнює . Алмаз є єдиним графом із характеристичним многочленом, що визначає граф за його спектром.
Примітки
Література
- ↑ Шаблон:MathWorld
- ↑ ISGCI: Information System on Graph Classes and their Inclusions "List of Small Graphs Шаблон:Webarchive".
- ↑ Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". Шаблон:Cite web Шаблон:Webarchive