δ(G) ≥ k − 1, то есть любая вершина смежна по меньшей мере k − 1 другим вершинам. Более строго, Gрёберно (k − 1)-связен[3].
Если граф G(k − 1)-регулярен (каждая вершина смежна в точности k − 1 другим), то граф G либо является полным графом Kk, либо нечётным циклом. (Это теорема Брукса[4]).
Либо G может быть разбит на два меньших критических графа с ребром между каждой парой вершин, где две вершины берутся из разных частей, либо граф G имеет по меньшей мере 2k — 1 вершин[7]. Более строго, либо G имеет разложения такого типа, либо для каждой вершины v графа G существует k-раскраска, в которой v является единственной вершиной со своим цветом, а все остальные классы цветов имеют по меньшей мере две вершины[8].
Граф G является вершинно критическим тогда и только тогда, когда для любой вершины v существует оптимальная подходящая раскраска, в которой вершина v одна представляет класс цвета.
1-критических графов не существует.
Единственный 2-критический граф — это K2.
Все 3-критические графы исчерпываются простыми циклами нечётной длины[9].
Как показал Хаджос[10], любой k-критический граф может быть сформирован из полного графаKk путём комбинации построения Хайоша с операцией отожествления двух несмежных вершин. Граф, образованный таким образом, всегда требует k цветов в любой правильной раскраске.
4-критический, но не рёберно-критический граф, поскольку
Хотя каждый рёберно-критический граф обязательно является критическим, обратное неверно. Например, граф представленный справа, является 4-критическим, но не рёберно-критическим[11].
Вариации и обобщения
Дважды критический граф — это связный граф, в котором удаление любой пары смежных вершин уменьшает хроматическое число на два. Одна из нерешённых задач — является ли Kk единственным дважды критическим k-хроматическим графом[12].
↑Следует отметить, что не всегда под критическим графом понимается критический k-хроматический граф. В статье Визинга под критическим графом размерности k понимается граф, у которого размерность любой собственной части меньше k. Под размерностью графа при этом понимается минимальная размерность метрического пространства, в которое можно вложить граф так, что все смежные вершины окажутся на расстоянии 1. (Визинг 1968)
R. L. Brooks, W. T. Tutte. On colouring the nodes of a network // Proceedings of the Cambridge Philosophical Society. — 1941. — Т. 37, вып. 02. — С. 194–197. — doi:10.1017/S030500410002168X.
N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54. — С. 371–373.. (Indag. Math.13.)
G. A. Dirac. A theorem of R. L. Brooks and a conjecture of H. Hadwiger // Proceedings of the London Mathematical Society. — 1957. — Т. 7, вып. 1. — С. 161–195. — doi:10.1112/plms/s3-7.1.161.
T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963a. — Т. 8. — С. 165–192.
T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963b. — Т. 8. — С. 373–395..
G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10. — С. 116–117.
László Lovász. Combinatorial Problems and Exercises (Second Edition). — North-Holland, 1992.
Paul Erdős. In Theory of Graphs. — Proc. Colloq., Tihany, 1966. — С. 361.
В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи Математических Наук. — 1968. — Т. XXIII, вып. 6 (144). — С. 117–134.
Ф. Харари. Теория графов. — 2-е. — М.: Едиториал УРСС, 2003. — ISBN 5-354-00301-6, ББК 22.144, 22.18, 22.19.
Похожие исследовательские статьи
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
В теории графов рёберным графомL(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в различных цветов для заданного значения или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.
В теории графов мультиграфами Шеннона называется специальный вид треугольных графов, которые используются при исследовании рёберной раскраски. Визинг назвал эти графы в честь Клода Шеннона.
Мультиграфы Шеннона — это мультиграфы с тремя вершинами, для которых выполняется одно из следующих условий:
a) все три вершины соединены одним и тем же числом рёбер.
b) так же, как в a) но добавлено ещё одно дополнительное ребро.
В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов.
Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов.
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Фактор-критический граф — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание.
Гипотеза Эрдёша — Фабера — Ловаса — это проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972 году. Гипотеза гласит:
Если k полных графов, каждый из которых имеет в точности k вершин, обладают свойством, что любая пара полных графов имеет не более одной общей вершины, то объединение графов может раскрашено в k цветов.
Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Визинг и Эрдёш, а также Рубин и Тейлор в 1970-х годах.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
