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

Граф «Лестница»

Вершин	2n
Рёбер	n+2(n-1)
Хроматическое число	2
Хроматический индекс	3 для n>2 2 для n=2 1 для n=1
Свойства	граф единичных расстояний гамильтонов планарный двудольный
Обозначение	L_n
Медиафайлы на Викискладе

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

Лестницу можно получить как прямое произведение двух путей, один из которых имеет только одно ребро — L_n = P_n × P₁ ^[2]^[3]. Если добавить ещё два пересекающихся ребра, соединяющих четыре вершины лестницы со степенью два, получим кубический граф — лестницу Мёбиуса.

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

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

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

Кольцевой лестничный граф CL_n — это прямое произведение цикла длины n≥3 и ребра ^[4]. В символьном виде CL_n = C_n × P₁. Граф имеет 2n вершин и 3n рёбер. Подобно лестницам граф является связным, планарным и гамильтоновым, но граф является двудольным тогда и только и тогда, когда n чётно.

Галерея

Хроматическое число лестницы равно 2.

Примечания

↑ Weisstein, Eric W. Ladder Graph (англ.) на сайте Wolfram MathWorld.
↑ Hosoya, Harary, 1993, с. 211-218.
↑ Noy, Ribó, 2004, с. 350-363.
↑ Chen, Gross, Mansour, 2013, с. 32–57.

Литература

H. Hosoya, F. Harary. On the Matching Properties of Three Fence Graphs // J. Math. Chem.. — 1993. — Вып. 12. — С. 211-218.
M. Noy, A. Ribó. Recursively Constructible Families of Graphs // Adv. Appl. Math. — 2004. — Вып. 32. — С. 350-363.
Yichao Chen, Jonathan L. Gross, Toufik Mansour. Total Embedding Distributions of Circular Ladders // Journal of Graph Theory. — 2013. — Т. 74, вып. 1. — С. 32–57. — doi:10.1002/jgt.21690.

Похожие исследовательские статьи

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

В теории графов нечётные графы O_n — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

<span class="mw-page-title-main">Граф Грёча</span> граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5

Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.

В теории графов колесом W_n называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла. Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их W_n означает граф W_n+1 по определению выше. Колесо может быть определено также, как 1-скелет (n-1)-угольной пирамиды.

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

<span class="mw-page-title-main">Граф гиперкуба</span> регулярный граф с 2^n вершинами, 2^(n−1)n рёбрами и n рёбрами, сходящимися в одной вершине

В теории графов графом гиперкуба Q_n называется регулярный граф с 2ⁿ вершинами, 2ⁿ⁻¹n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q₃ — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

<span class="mw-page-title-main">Лестница Мёбиуса</span> кубический циркулянтный граф

Ле́стница Мёбиуса $\text{[math]}$ — кубический циркулянтный граф с чётным числом вершин $\text{[math]}$ , образованный из цикла с $\text{[math]}$ вершинами путём добавления рёбер, соединяющих противоположные пары вершин цикла. Назван так ввиду того, что $\text{[math]}$ состоит из $\text{[math]}$ циклов длины 4, соединённых вместе общими рёбрами и образующих топологически ленту Мёбиуса. Полный двудольный граф $\text{[math]}$ является лестницей Мёбиуса $\text{[math]}$ .

Граф Вагнера — 3-регулярный граф с 8 вершинами и 12 рёбрами, является 8-вершинной лестницей Мёбиуса.

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

Граф Татта — пример кубического полиэдрального графа, не являющегося гамильтоновым. Таким образом, он служит контрпримером к гипотезе Тэйта, предполагавшей, что любой 3-регулярный многогранник имеет гамильтонов цикл.

В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Файл назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом. Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.

В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.

Граф призмы — рёберный граф одной из призм.

Граф дружеских отношений F_n — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.

Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами. Граф представляет собой полный граф $\text{[math]}$ без одного ребра.

Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.