Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон





















Яндекс.Метрика

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


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

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

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

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

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

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

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

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

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

Имя:*
E-Mail:
Комментарий: