По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются)[4]. Кроме того, в этом случае применима теорема Татта.
Теорема Робертсона — Сеймура гарантирует, что тороидальные графы можно определить конечным набором запрещённых графов. Однако набор запрещённых графов в этом случае неизвестен, и их число не менее 250815[6].
Примеры
Любой граф с числом пересечений равным 1 тороидален.
Endo, Toshiki. The pagenumber of toroidal graphs is at most seven // Discrete Mathematics. — 1997. — Vol. 175, no. 1–3. — P. 87—96. — doi:10.1016/S0012-365X(96)00144-6.
Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan. Discrete one-forms on meshes and applications to 3D mesh parameterization // Computer Aided Geometric Design. — 2006. — Vol. 23, no. 2. — P. 83—112. — doi:10.1016/j.cagd.2005.05.002.
Heawood P. J. Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Vol. 24. — P. 322—339.
Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с моделью Поттса статистической физики.
Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
Индекс Винера — топологический индекс неориентированного графа , определяемый как сумма длин кратчайших путей между вершинами графа:
.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.
Веретено Мозера — неориентированный граф, названный в честь математиков Лео Мозера и его брата Вильяма, имеющий семь вершин и одиннадцать рёбер. Он является графом единичных расстояний, требующим четыре цвета в любой раскраске, и его существование используется для доказательства того, что хроматическое число плоскости равно по меньшей мере четырём.
Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена , то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.
Граф ТуранаT(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь подмножеств размером и подмножеств размером . Таким образом, это полный r-дольный граф
LCF-код — система обозначений в комбинаторной математике, разработанная Ледербергом и расширенная Коксетером и Фрухтом, для представления кубических графов, являющихся гамильтоновыми . Поскольку графы гамильтоновы, вершины можно расположить на окружности, которая задаёт два ребра для каждой вершины. Третье ребро можно теперь описать количеством позиций, на которые отстоит конец ребра от начала. Часто в результате получаем повторяющуюся последовательность чисел, в этом случае выписывается только эта повторяющаяся часть, а число повторений показывается верхним индексом. Например, Граф Науру имеет LCF-код [5, −9, 7, −7, 9, −5]4. Один и тот же граф может иметь различные LCF-коды в зависимости от того, как вершины будут расположены на окружности.
Ле́стница Мёбиуса — кубический циркулянтный граф с чётным числом вершин , образованный из цикла с вершинами путём добавления рёбер, соединяющих противоположные пары вершин цикла. Назван так ввиду того, что состоит из циклов длины 4, соединённых вместе общими рёбрами и образующих топологически ленту Мёбиуса. Полный двудольный граф является лестницей Мёбиуса .
В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.
Теорема Фляйшнера — утверждение в теории графов, дающее достаточное условие, чтобы граф содержал гамильтонов цикл: если граф является вершинно 2-связным графом, то квадрат графа гамильтонов. Названа именем Герберта Фляйшнера, опубликовавшего доказательство теоремы в 1974 году.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф Gk-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
Степень k неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом.
110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.
Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.
Граф Голомба — полиэдральный граф с 10 вершинами и 18 рёбрами. Граф назван именем Соломона Вольфа Голомба, который построил его как граф единичных расстояний, который требует четыре цвета для раскраски. Таким образом, подобно более простому веретену Мозера, граф даёт нижнюю границу для задачи Нелсона — Эрдёша — Хадвигера — раскраска точек евклидовой плоскости, так что единичный отрезок имеет различные цвета на концах, требует по меньшей мере четырёх цветов.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
