Связанные понятия
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Подробнее: Циркулянтный граф
Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.
Подробнее: Компонента сильной связности в орграфе
В теории графов
глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Подробнее: Рёберный граф
В теории графов
хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором любое минимальное вершинное покрытие имеет один и тот же размер (как и любое другое минимальное вершинное покрытие). Хорошо покрытые графы определил и изучал Пламмер.
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
Подробнее: Нечётный граф
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Два-граф ы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна...
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Лемма берёт название от популярной аналогии: в группе людей, некоторые из которых пожимают друг другу руки, чётное число людей поприветствовало таким образом нечётное число коллег.
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов.
Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.)
В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k.
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций...
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Подробнее: Граф без клешней
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса (иногда называемого оптимальным ветвлением).
Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.
Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения (никакой интервал не содержит какой-либо другой). Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными...
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
Окрестность часто обозначается как NG(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как NG. Если не указано явно, окрестность...
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Совершенная (или грациозная) разметка рёбер графа — это вид разметки графа. Это разметка для простых графов (в простом графе никакие два различных ребра не соединяют те же самые две различные вершины, никакое ребро не соединяет вершину с ней же (нет петель) и граф связен). Совершенные разметки рёбер ввёл в своей статье С. Ло.
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нила Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.
Подробнее: Порождённый путь
Одновременное вложение графов — это техника визуализации двух и более различных графов на одном и том же множестве помеченных вершин, при которой избегается пересечения рёбер в каждом из графов. Пересечения между рёбрами разных графов разрешаются, не разрешается только пересечение рёбер одного графа.
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Подробнее: Мультиграф
Структурная теорема графов — это главный результат в области теории графов. Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями. Теорема была сформулирована в семнадцати статьях из серии из 23 статей Нейла Робертсона и Пола Сеймура. Доказательство теоремы очень длинно и запутано. Каварабайаши и Мохар и Ловаш провели обзор теоремы в доступном для неспециалистов виде, описав теорему и её следствия.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Подробнее: Граф пересечений