Алмаз (теорія графів)
| Алмаз | |
|---|---|
 | |
| Вершин | 4 |
| Ребер | 5 |
| Радіус | 1 |
| Діаметр | 2 |
| Обхват | 3 |
| Автоморфізм | 4 (Z/2Z×Z/2Z) |
| Дробово-хроматичне число | 3 |
| Дробово-хроматичний індекс | 3 |
| Властивості |
Граф одиничних відстаней Планарний Гамільтонів |
Алмаз — це планарний неорієнтований граф із 4 вершинами та 5 ребрами[1][2]. Граф являє собою повний граф без одного ребра.
Радіус алмаза дорівнює 1, діаметр дорівнює 2, обхват дорівнює 3, хроматичний індекс і хроматичне число дорівнюють 3. Граф також вершинно 2-зв'язаний і реберно 2-зв'язаний, має граціозну розмітку[3] і є гамільтоновим.
Графи без алмазів і заборонені мінори[ред. | ред. код]
Граф є вільним від алмазів, якщо він не містить алмаза в якості породженого підграфа. Графи без трикутників є вільними від алмазів, оскільки будь-який алмаз містить трикутник.
Сімейство графів, в якому кожна зв'язна компонента є кактусом, замкнуто донизу відносно операції утворення мінору графа. Це сімейство графів може бути описано єдиним забороненим мінором — алмазом[4].
Якщо метелик й алмаз є забороненими мінорами, отримане сімейство графів є сімейством псевдолісів.
Алгебраїчні властивості[ред. | ред. код]
Група автоморфізмів алмаза є групою порядку 4, ізоморфною четверній групі Клейна, прямому добутку циклічної групи Z/2Z на себе.
Характеристичний многочлен алмаза дорівнює . Алмаз є єдиним графом із характеристичним многочленом, що визначає граф за його спектром.
Примітки[ред. | ред. код]
- ↑ Weisstein, Eric W. Diamond Graph(англ.) на сайті Wolfram MathWorld.
- ↑ ISGCI: Information System on Graph Classes and their Inclusions "List of Small Graphs [Архівовано 22 липня 2012 у Wayback Machine.]".
- ↑ Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". Архівована копія (PDF). Архів оригіналу (PDF) за 7 серпня 2008. Процитовано 16 вересня 2009.
{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) - ↑ El-Mallah, Colbourn, 1988, с. 354–362.
Література[ред. | ред. код]
- 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:.