Определение: |
Подмножество вершин графа называется независимым, если любые две вершины из не смежны в |
Определение: |
Число независимости графа — и независимо в G |
Лемма (нижняя оценка): |
Пусть — произвольный связный неориентированный граф с вершинами.Тогда, . |
Доказательство: |
Пусть, множеств вершин окрашенных в соответствующие цвета при правильно покраски графа .Каждое из — независимое множество (поскольку вершины множества покрашены в один цвет при правильной покраски графа , следовательно, они попарно не смежны внутри множества). Заметим, что для произвольного , (т.к независимое множество). То есть, , следовательно . |
8.2 Конструирование хроматического полинома
Теорема (Зыкова): |
Для хроматического многочлена графа верна формула: , где — число способов разбить вершины на независимых множеств, , а — нисходящая факториальная степень. |
Доказательство: |
В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской доступными цветами получим искомое число способов раскраски графа в цветов. Теперь проделаем это более формально. Подсчитаем число раскрасок графа , в которых используется точно цветов, для этого его нужно разбить на независимых множеств и вершины в каждом таком классе покрасить в один из цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами. Рассмотрим случай, где . Чтобы получить такую раскраску зафиксируем какое-нибудь разбиение множества вершин графа на независимых множеств, затем берем один из классов в разбиении и раскрашиваем его в один из цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из оставшихся красок и т.д. Всего таких способов разбиения существует . Следовательно, перебрав все возможные разбиения на независимых множеств, получим, что число интересующих нас раскрасок графа равно . Заметим теперь, что при число -раскрасок, в которых используется точно цветов, равно и при этом тоже равно . Суммирование по от до даст полное число способов. |
https://www.allmath.ru/highermath/algebra/graph/graph5.htm
8.3 Теорема Кёнига о бихроматических графах
Теорема: |
Граф -раскрашиваемый тогда и только тогда, когда он двудольный. |
Доказательство: |
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф — -раскрашиваем. . Если же граф -раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны. |
8.4 Алгоритм построения правильной раскраски.
8.5 Теорема Хивуда о раскраске планарного графа
https://kadm.imkn.urfu.ru/files/tgr13.pdf
8.6 Раскраска карт.
Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски карты на плоскости эквивалентна задаче на сфере.
8.7 Теоремы Шеннона и Визинга о хроматическом классе.
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большего максимальной степени вершин А δ {\displaystyle \delta } графа. Поскольку по меньшей мере А δ {\displaystyle \delta } цветов необходимо всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых А δ {\displaystyle \delta } цветов достаточно, и «второго класса», для которых необходимо А+1 δ + 1 {\displaystyle \delta +1} цветов.
Результат установлен Вадимом Визингом в 1964 году.
https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%92%D0%B8%D0%B7%D0%B8%D0%BD%D0%B3%D0%B0#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D1.8B
https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%B3%D1%80%D0%B0%D1%84_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0#CITEREFShannon1949