В поисках хроматического числа

Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов. Подробнее об этом по просьбе N + 1 рассказал математик Владимир Потапов.

Хроматическое число графов

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

Начнем с того, что графом в математике называется набор точек (вершин графа), соединенных отрезками (ребрами графа). Раскраска вершин графа в разные цвета называется правильной, если вершины, соединенные ребром (смежные вершины), раскрашены в разные цвета.

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

Задача нахождения хроматического числа графа стала популярной благодаря широко известному вопросу: «Можно ли вершины плоского (то есть размещенного на плоскости без пересечений ребер) графа правильно раскрасить в 4 цвета?»

Гипотеза «четырех красок», которая состоит в положительном ответе на этот вопрос, возникла еще в XIX веке и была доказана Кеннетом Аппелем и Вольфгангом Хакеном только в 1977 году. Причем в доказательстве авторам пришлось прибегнуть к компьютеру, чтобы правильно раскрасить сотни графов, раскраска которых уже не сводилась к раскраске более простых графов. Кстати, граф Петерсена плоским не является и может быть нарисован на плоскости только с пересечениями ребер.

Может показаться, что игры в раскрашивание графов не могут иметь никакого полезного применения. Даже практический вопрос: сколько необходимо цветов, чтобы любые соседние страны на карте были разного цвета? — из которого возникла гипотеза о «четырех красках», кажется скорее праздным, чем полезным. Однако по мере роста сложности инфраструктуры и оборудования оказалось, что имеется множество вполне серьезных задач, которые сводятся к нахождению хроматического числа графа.

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

Если же рассмотреть социальную сеть Facebook как граф с вершинами — пользователями, каждая из которых смежна с «друзьями», то становится ясно, что изучение различных характеристик графов важно для понимания закономерностей распространения информации (новостей, моды, инноваций) в современном мире.

Произведения графов

Прежде чем перейти к обсуждению гипотезы Хидетниеми, поговорим о понятии декартова произведения графов. Пусть имеются два графа G и H с множествами вершин {u₁…u_n} и {v₁…v_m} соответственно. Тогда их декартовым произведением называется граф, вершины которого являются всевозможными парами (u_i,v_k). Причем вершины (g,h) и (b,d) соединены ребром, только если g=b и вершина h смежна с вершиной d в графе H или, наоборот, h=d и вершина g смежна с вершиной b в графе G.

Легко понять, что хроматическое число декартова произведения графов не меньше, чем хроматическое число любого из сомножителей. Если мы зафиксируем любую вершину h графа H и рассмотрим в декартовом произведении вершины вида (u,h), а также ребра между ними, то получится такой же подграф, как граф G. Значит, для правильной раскраски этого подграфа нужно столько же цветов, сколько для правильной раскраски графа G, а для правильной раскраски всего декартова произведения цветов нужно точно не меньше. То же самое можно сказать и про граф H.

Более 50 лет назад математик Герт Сабидусси доказал, что хроматическое число декартова произведения графов равно максимуму хроматических чисел сомножителей.

Теперь перейдем к тензорному произведению графов, о котором говорится в гипотезе Хидетниеми. Тензорным произведением графов G и H называется граф с теми же вершинами, что и у декартова произведения графов G и H, которые, однако, по-другому соединены ребрами. А именно, вершины (g,h) и (b,d) в тензорном произведении соединены ребром, только если вершина g смежна с вершиной b в графе G и вершина h смежна с вершиной d в графе H.

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

Действительно, если покрасить каждую вершину (u,v) тензорного произведения в тот цвет, в который была покрашена вершина u графа G, то любая смежная с ней вершина (g,h) окажется покрашена в другой цвет, поскольку вершины u и g были смежны в графе G и его раскраска была правильной. Значит, цвета вершин (u,v) и (g,h), так же как вершин u и g, различны. Поэтому хроматическое число тензорного произведения не превосходит минимума хроматических чисел сомножителей.

Сильным произведением двух графов G₁ и G₂ называется граф с тем же множеством вершин, как у декартова и тензорного произведения этих графов. Ребрами сильного произведения графов являются одновременно ребра декартова и тензорного произведений.

Гипотеза Хидетниеми и ее опровержение

Естественно предположить, что хроматическое число тензорного произведения будет в точности равно минимуму хроматических чисел сомножителей. Ведь каждая вершина тензорного произведения графов имеет гораздо больше соседей, чем было у вершин исходных графов! Тем более что в похожем случае декартова произведения имеется равенство.

Это естественное предположение и сделал Хидетниеми. И оно подтверждалось практически для различных частных случаев, Например, граф на иллюстрации выше имеет циклы нечетной длины, а значит, его хроматическое число не меньше трех. И даже теоретически для некоторых классов графов было доказано, что гипотеза Хидетниеми верна, например для тензорного произведения любых двух графов с хроматическими числами не более 4.

Круг графов, для которых удалось проверить правильность гипотезы Хидетниеми постепенно расширялся и казалось, что вот-вот гипотеза будет доказана полностью.

Однако Ярославу Шитову неожиданно удалось доказать обратное. Причем не посредством построенного с помощью компьютера контрпримера, а полностью теоретически.

Для того чтобы кратко описать его доказательство, нам понадобится несколько определений. Во-первых, для произвольного графа H определим экспоненциальный граф E_s(H). Вершинами графа E_s(H) будут функции, действующие из множества вершин графа H в множество чисел {1, …, s}. Две функции f и g будем считать смежными, если они принимают различные значения на любых вершинах, смежных в графе H.

Нетрудно убедиться, что тензорное произведение графов H и E_s(H) можно правильно раскрасить в s цветов, независимо от хроматического числа графа H. Определим раскраску вершины (u,f) тензорного произведения равной f(u). Рассмотрим пару вершин (u,f) и (v,g) смежных в тензорном произведении графов. Тогда вершины u и v смежны в H, а вершины f и g смежны в E_s(H). Значит, по определению экспоненциального графа числа f(u) и g(v) не совпадают, то есть так определенная раскраска тензорного произведения в s цветов является правильной.

Теперь нужно найти подходящий граф H, чтобы хроматические числа графа H и его экспоненциального графа E_s (H) были строго больше s.

Классическая теорема Пала Эрдеша утверждает, что найдутся графы со сколь угодно большим хроматическим числом и сколь угодно большим обхватом (минимальным циклом).

Рассмотрим граф G с обхватом 10 и хроматическим числом 5. Полным графом K_q, или q-кликой, называется граф на q вершинах, все вершины которого попарно соединены ребрами.

Определим граф H как сильное произведение графов G и K_q. Граф H получается подстановкой q-клик во все вершины графа G, причем все вершины смежных q-клик попарно соединены ребрами. Отсюда нетрудно доказать, что хроматическое число сильного произведения графа G на q-клику будет иметь хроматическое число не меньше чем 5q.

Ярославу Шитову удалось доказать, что для достаточно больших q и s > 4,1q экспоненциальный граф E_s(H) имеет хроматическое число строго большее, чем s. Теперь достаточно выбрать такое s, что 5q > s > 4,1q и мы получаем, что оба сомножителя H и E_s(H) в тензорном произведении имеют хроматические числа больше, чем s, а их тензорное произведение имеет хроматическое число равное s, как было доказано выше. Таким образом, гипотеза Хидетниеми опровергнута.

Владимир Потапов