Лестница в теории графов — планарный неориентированный граф с вершинами и рёбрами.
Лестницу можно получить как прямое произведение двух путей, один из которых имеет только одно ребро — Ln = Pn × P1 . Если добавить два пересекающихся ребра, соединяющих четыре вершины лестницы со степенью два, получим кубический граф — лестницу Мёбиуса.
По построению, лестница изоморфна решётке и выглядит как лестница с перекладинами. Граф является гамильтоновым с обхватом 4 (если ) и хроматическим индексом 3 (если ).
Хроматическое число лестницы равно 2, а её хроматический многочлен равен .
Кольцевой лестничный граф — прямое произведение цикла длины и ребра : . Имеет вершин и рёбер. Подобно лестницам граф является связным, планарным и гамильтоновым, но при этом является двудольным тогда и только и тогда, когда чётно.
Галерея
Примечания
Литература
Категория:Параметрические семейства графов Категория:Планарные графы Категория:Графы с хроматическим числом 2