|
|
 |
Условие
Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества {1, 2, 3, ..., 2k}, а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.
Решение
Пусть – число вершин нашего графа G, то есть количество троек элементов из множества из множества {1, ..., n}. Минимальное число цветов χ(G), в которые можно правильно раскрасить вершины, называется хроматическим числом графа.
Покажем, что χ(G) ≥ ⅙ (n – 1)(n – 2). Пусть S – максимальное число вершин графа, попарно не соединенных рёбрами. Поскольку вершин каждого цвета не больше S, то S·χ(G) ≥ N = ⅙ n(n – 1)(n – 2).
Остаётся проверить, что S ≤ N.
Но это доказано в решении задачи 97876 (где ученики – элементы нашего множества, а кружки – трёхэлементные подмножества).
Итак, нижняя оценка получена. Докажем, что при n = 2k она точна.
Покажем, как раскрасить вершины графа в χ = ⅙ (n – 1)(n – 2) цветов. Закодируем элементы множества {1, 2, ..., n} всевозможными последовательностями вида x = (x1, ..., xk) длины k, состоящими из нулей и единиц. Тогда вершина графа – это тройка таких последовательностей {a1, a2, a3}. Сопоставим вершине графа v тройку b(v) = {b1, b2, b3}, где b1 = a2 + a3, b2 = a3 + a1, b3 = a1 + a2 – суммы по модулю два. Ясно, что среди последовательностей b1, b2, b3 нет совпадающих. Значит, b(v) является множеством из трёх различных элементов. Каждому набору вида b(v) присвоим уникальный цвет, таким
образом получая раскраску вершин исходного графа. Заметим, что если две вершины u, v графа пересекаются ровно по одному элементу, то соответствующие им тройки b(u), b(v) различны. Следовательно, полученная раскраска допустима. Осталось посчитать количество использованных цветов. Нетрудно видеть, что
1) ни одна из последовательностей b1, b2, b3 не совпадает с последовательностью 0, состоящей из одних нулей;
2) b1 + b2 + b3 = 2a1 + 2a2 + 2a3 = 0 (mod 2);
3) любой набор, состоящий из трёх различных последовательностей b1, b2, b3, который удовлетворяет предыдущим двум пунктам, может быть получен из некоторой вершины графа описанным выше способом: для этого достаточно рассмотреть вершину {0, b3, b2}.
Таким образом, b1 можно выбрать n – 1 способом, b2 – n – 2 способами, а b3 однозначно по ним определяется. Поскольку тройки неупорядоченные, полученный результат (n – 1)(n – 2) следует разделить на 6. Итак, количество различных троек {b1, b2, b3}, сопоставленных вершинам графа, равно χ, то есть мы раскрасили вершины в χ цветов.
Ответ
⅙ (2k – 1)(2k – 2) цветов.
