Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Полезные советы




29.12.2022


29.12.2022


23.12.2022


25.11.2022


08.11.2022


08.11.2022





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





Лестница (теория графов)

25.12.2022

В теории графов лестница Ln — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами .

Лестницу можно получить как прямое произведение двух путей, один из которых имеет только одно ребро — Ln = Pn × P1 . Если добавить ещё два пересекающихся ребра, соединяющих четыре вершины лестницы со степенью два, получим кубический граф — лестницу Мёбиуса.

По построению, лестница Ln изоморфна решётке G2,n и выглядит как лестница с n перекладинами. Граф является гамильтоновым с обхватом 4 (если n>1) и хроматическим индексом 3 (если n>2).

Хроматическое число лестницы равно 2, а её хроматический многочлен равен ( x − 1 ) x ( x 2 − 3 x + 3 ) ( n − 1 ) {displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}} .

Кольцевой лестничный граф

Кольцевой лестничный граф CLn — это прямое произведение цикла длины n≥3 и ребра . В символьном виде CLn = Cn × P1. Граф имеет 2n вершин и 3n рёбер. Подобно лестницам граф является связным, планарным и гамильтоновым, но граф является двудольным тогда и только и тогда, когда n чётно.

Галерея

Лестница L1, L2, L3, L4 и L5.
  • Хроматическое число лестницы равно 2.


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