Раскрашивание графа — Теория графов

Когда мы присваиваем вершинам графа метки — это называется раскраской графов.

Цвета — это целые положительные цифры. Графы нужно раскрашивать так, чтобы соседние вершины имели разные цвета. Еще стоит использовать как можно меньше цветов.

Вот несколько примеров раскраски графа:

Первый пример на схеме выше не совсем верный, потому что соседним вершинам присваивается один и тот же цвет. Вторая раскраска лучше, так как удовлетворяет правилам, но в ней используется больше цветов, чем нужно. Третья раскраска — правильная. Она удовлетворяет правилам и использует как можно меньше цветов.

В этих графах невозможно использовать меньше трех цветов, так как треугольники содержат три вершины, которые являются соседями.

Хроматическое число графа , которое обозначается — это минимальное количество цветов, необходимое для правильной раскраски графа.

Чтобы обозначить, о каком графе идет речь, мы будем сокращенно обозначать как . Рассмотрим раскраску графов на просто классе графов — путях.

Вот несколько оптимальных вариантов раскраски путей:

В общем случае для каждого .

Рассмотрим другие примеры:

Четные и нечетные циклы ведут себя по-разному. У нечетных всегда хроматическое число три, а у четных — хроматическое число два.

Теперь рассмотрим, как раскрашивают полные графы.

У нас есть следующие полные графы с уже помеченными вершинами:

Поскольку в полном графе каждая вершина смежна с любой другой вершиной, мы не можем повторить ни одного цвета. Таким образом, .

Рассмотрим следующие примеры:

На графиках видно, что соседние вершины раскрашены в один цвет. В случае с двудольными графами такое возможно, так как применяется правило партитного множества — независимое множество, между вершинами которого нет ребер. Поэтому мы можем окрасить все его вершины в один цвет.

Для двух партитных множеств нужно два цвета. И это относится к любому двудольному графу, а не только к полному.

Любой граф с хотя бы одним ребром является двудольным, когда он двухцветный. Поскольку деревья двудольные, мы теперь знаем, что все нетривиальные деревья имеют хроматическое число .

Мы пришли к такой формуле:

Это связано с тем, что между копиями и в объединении нет ребер. Поэтому мы можем раскрасить каждый граф отдельно, и не беспокоиться:

Мы также имеем — каждая вершина смежна с каждой вершиной . Поэтому ни один цвет, который используется на , не может быть использован на и наоборот.

Обратите внимание на второй граф на схеме выше. Чтобы получить правильную раскраску , мы можем раскрасить и отдельно, а затем заменить каждый цвет из на .

Декартово произведение немного сложнее. Результат , что совпадает с результатом для объединения.

Рассмотрим пример: . Ниже выделена конкретная вершина:

Выделенная вершина — это часть сразу двух графов ( и ). Нам нужно убедиться, что ее раскраска работает в отношении обоих графов. Мы можем представить и как состоящий из пяти копий со связями между копиями, которые определяются связями .

Нам нужно раскрасить каждую из пяти копий по-своему и убедиться, что взаимодействия между копиями, которые определяются , соблюдены. Начнем с оптимальных раскрасок и :

Хитрость в том, чтобы для каждой вершины взять ее цвет в , ее цвет в и сложить их. При этом нужно уменьшить результат по модулю и заменить все полученные нули тройками. В итоге раскраски для пяти копий выглядят следующим образом:

Такой способ гарантирует, что соседние вершины никогда не будут иметь одинаковый цвет. Этот же процесс работает и в общем случае:

Вот еще один пример раскраски графа без очевидной структуры:

Может потребоваться некоторое усилие, чтобы придумать ответ к такой неочевидной структуре. Пройдем этот процес по шагам:

В этом уроке мы разобрали, что такое раскраска графов и как это относится к цифрам на вершинах. Мы показали, как раскрашивать графы разных типов. В каждом случае этот процесс немного отличается, при этом везде соблюдается правило соседних вершин.