Главная
В теории графов лестница 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.