Задача 047 — Задачи на Графы

Вершины графа разбиты на три множества $A, B, C$ так, что вершины из $A$ не связаны рёбрами с вершинами из $C$ . Известно, что $A \cup B$ можно правильно раскрасить в $k$ цветов, а $B \cup C$ — в $n$ цветов. В какое минимальное количество цветов можно с гарантией правильно раскрасить все вершины этого графа?

Подсказка

Покажите, что в $k+n-1$ цвет правильно раскрасить все вершины можно всегда.

Решение

Ответ. В $k+n-1$ цвет.

Решение: Покажем, что в $k+n-1$ цвет правильно раскрасить все вершины можно всегда. Раскрасим $B \cup C$ в $n$ цветов, назовём один из этих цветов первым, и пусть $D$ — совокупность всех вершин из $B$ , покрашенных в первый цвет. Теперь раскрасим $A \cup D$ в $k$ цветов, использовав в качестве одного из них первый цвет (а остальные $k-1$ цветов взяв отличными от уже использованных $n$ цветов). У вершин, не входящих в $A \cup D$ , сохраним прежнюю раскраску. Поскольку никакие вершины из $A \cup D$ не связаны рёбрами с вершинами из $C$ , покрашенными в первый цвет (из $D$ — в силу правильности раскраски $B \cup C$ в $n$ цветов, из $A$ — по условию), получится правильная раскраска графа в $k+n-1$ цвет.

Теперь покажем, что меньшего числа цветов может и не хватить. Расположим $k n$ точек в виде прямоугольника из $n$ строк и $k$ столбцов. Примем это множество за $B$ . Снизу добавим нулевую строку из $k$ точек, примем ее за $A$ , слева нулевой столбец, примем его за $C$ . Ребрами в $B$ соединим любые две точки, не лежащие ни в одной строке, ни в одном столбце. В $A$ соединим рёбрами каждые две точки, в $C$ — тоже. Кроме того, соединим рёбрами каждую точку из $A$ со всеми точками из $B$ , не лежащими с ней в одном столбце, и каждую точку из $C$ со всеми точками из $B$ , не лежащими с ней в одной строке. Очевидны правильные раскраски $A \cup B$ в $k$ цветов (по столбцам) и $C \cup B$ в $n$ цветов (по строкам). Покажем, что полученный граф нельзя раскрасить меньше, чем в $k+n-1$ цвет. Допустим, есть правильная раскраска $A \cup B \cup C$ в $k+n-2$ цвета. Поскольку точки множества $A$ раскрашены в $k$ различных цветов, а точки множества $C$ — в $n$ различных цветов, то есть $m \geq 2$ цветов (назовём их общими), в которые покрашены точки обоих этих множеств. Отметим строки и столбцы, в которых находятся такие точки; на их пересечении находится $m^{2}$ точек множества $B$ . Заметим, что в каждый из $m$ общих цветов может быть покрашено не больше одной из этих $m^{2}$ точек, а именно, точка, стоящая на пересечении соответствующих столбца и строки. Стало быть, среди этих $m^{2}$ точек есть $m^{2}-m$ точек, раскрашенных в другие цвета. Это не могут быть общие цвета, но не могут быть и другие цвета, использованные при раскраске точек множеств $A$ и $C$ , потому что со всеми точками таких цветов точки из отмеченных строк и столбцов связаны рёбрами. Всего при раскраске точек из $A$ и $C$ было использовано $k+n-m$ цветов. Из упомянутых выше $m^{2}-m$ точек можно выбрать $m$ точек, никакие две из которых не лежат в одной строке или одном столбце. Каждые две из этих $m$ точек связаны ребром, поэтому они раскрашены не менее, чем в $m$ цветов. Получается, что всего использовано не менее, чем $k+n$ цветов. Противоречие.