Связанные понятия
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k.
Дуговая диаграмма — это стиль представления графа, в котором вершины располагаются вдоль прямой на евклидовой плоскости, а рёбра рисуются в виде полуокружностей на одной из двух полуплоскостей, либо в виде гладких кривых, образованных полуокружностями. В некоторых случаях отрезки прямой также используются для представления рёбер графа, если они соединяют соседние вершины на прямой.
Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение...
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время...
Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.
В теории графов круговой граф — это граф пересечений множества хорд окружности. То есть это неориентированный граф, вершины которого можно отождествить с хордами окружности, и эти вершины смежны тогда и только тогда, когда соответствующие хорды пересекаются.
Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
В теории графов
глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...
Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна...
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев. Удаление любого ребра из T делит рёбра графа G на два подграфа, а шириной декомпозиции считается максимальное число общих вершин в любом подграфе, полученным таким образом.
В теории графов
хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором любое минимальное вершинное покрытие имеет один и тот же размер (как и любое другое минимальное вершинное покрытие). Хорошо покрытые графы определил и изучал Пламмер.
n-Мерная
целочисленная решётка (или кубическая решётка), обозначается Zn, — это решётка в евклидовом пространстве Rn, точки которой являются n-кортежами целых чисел. Двумерная целочисленная решётка называется также квадратной решёткой. Zn является наиболее простым примером решётки корней. Целочисленная решётка является нечётной унимодулярной решёткой.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Подробнее: Рёберный граф
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Два-граф ы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения (никакой интервал не содержит какой-либо другой). Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными...
В вычислительной геометрии и планировании движений роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать...
Подробнее: Граф видимости
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
В теории графов частичный куб — это подграф гиперкуба, сохраняющий расстояния (в терминах графов) — расстояние между любыми двумя вершинами подграфа, то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в...
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
Подробнее: Нечётный граф
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Подробнее: Циркулянтный граф
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
В теории графов древесная декомпозиция — это отображение графа в дерево, которое может быть использовано для определения древесной ширины графа и ускорения решения определённых вычислительных задач на графах.
В теории графов петерсеново семейство графов — это набор из семи неориентированных графов, включающий граф Петерсена и полный граф K6. Петерсеново семейство названо именем датского математика Юлиуса Петерсена, поскольку в набор входит граф Петерсена.
Структурная теорема графов — это главный результат в области теории графов. Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями. Теорема была сформулирована в семнадцати статьях из серии из 23 статей Нейла Робертсона и Пола Сеймура. Доказательство теоремы очень длинно и запутано. Каварабайаши и Мохар и Ловаш провели обзор теоремы в доступном для неспециалистов виде, описав теорему и её следствия.
Многоугольник Петри для правильного многогранника в размерности n — это пространственный многоугольник, такой что любые (n-1) последовательных ребра (но не n) принадлежат одной (n-1)-мерной грани.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Лемма берёт название от популярной аналогии: в группе людей, некоторые из которых пожимают друг другу руки, чётное число людей поприветствовало таким образом нечётное число коллег.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
Сильная ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация графа), при котором граф превращается в сильно связный граф.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...
Подробнее: Граф гиперкуба
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.