Связанные понятия
В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.
Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов.
Хромати́ческое число ́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
Слабая раскраска — это специальный вид разметки графа. Слабая k-раскраска графа G = (V, E) назначает цвета c(v) ∈ {1, 2, ..., k} всем вершинам v ∈ V, так что каждая неизолированная вершина смежна по меньшей мере одной вершине другого цвета. В формальных обозначениях, для любой неизолированной вершины v ∈ V существует вершина u ∈ U с {u, v} ∈ E и c(u) ≠ c(v).
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом...
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов.
Подробнее: Ациклическая раскраска графа
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.
Теорема Грёча — это утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках, для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета. По теореме же Грёча достаточно лишь три цвета для планарных графов, которые не содержат трёх связанных друг с другом вершин.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
В теории графов
теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети (которая может представлять собой улицы города или лабиринт). В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того...
Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок.
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов.
Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна...
Гипотеза Эрдёша — Фабера — Ловаса — это нерешённая проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972. Гипотеза гласит...
Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.
Подробнее: Гипогамильтонов граф
Задача Рамсея , задача о знакомствах среди шести человек — это математическая теорема в теории Рамсея, частный случай теоремы Рамсея.
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.
Подробнее: Медианный граф
Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...
Подробнее: Граф гиперкуба
Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.)
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами, рёбрами, вершинами, или рёбрам, и вершинам графа.
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.
Подробнее: Минор графа
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
Подробнее: Нечётный граф
В теории графов круговой граф — это граф пересечений множества хорд окружности. То есть это неориентированный граф, вершины которого можно отождествить с хордами окружности, и эти вершины смежны тогда и только тогда, когда соответствующие хорды пересекаются.
Кубический граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
Гипотеза Хивуда , или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Подробнее: Внешнепланарный граф
В теории графов
псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нила Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют вполне квазиупорядоченное множество. Эквивалентно, любое семейство графов, замкнутое по минорам, может быть определено конечным набором запрещённых миноров, аналогично как теорема Вагнера определяет планарные графы как графы, не имеющие в качестве миноров полный граф K5 и полный двудольный граф K3,3.
Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. (По теореме Визинга хроматический индекс кубического графа равен 3 или 4.) Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.
Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Гипотеза Албертсона — это недоказанная связь между числом пересечением и хроматическим числом графа. Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит, который сформулировал утверждение в качестве гипотезы в 2007. Гипотеза является одной из многих гипотез в теории раскраски графов. Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф Kn находится среди графов, имеющих наименьшее число пересечений.