Раскраска графов

 

Какого  цвета ребра могут соединять  вершины  ,   и  ? Если хотя бы одно из них окажется красным, как на рисунке,

 

то получится  треугольник с красными сторонами. Если же все эти ребра синие, как  на рисунке,

 

то они  вместе образуют "треугольник" с  синими сторонами.

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

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

Свойство 1. Любая вершина полного графа с шестью или более вершинами и ребрами двух цветов принадлежит, по меньшей мере, трем ребрам одного цвета.

Свойство 2. В любом полном графе с шестью или более вершинами и ребрами двух цветов найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Задача 2. На географической карте выбраны пять городов. Известно, что среди них из любых трех найдутся два, соединенные авиалиниями, и два — несоединенные. Требуется доказать, что:

1. Каждый город соединен авиалиниями непосредственно с двумя и только с двумя другими городами.
2. Вылетев из любого города, можно облететь остальные, побывав в каждом по одному разу, и вернуться назад.

Решение. Рассматривается множество объектов — городов и два отношения, заданные для элементов этого множества. Каждые два города находятся в одном из двух отношений — они либо соединены между собой авиалиниями, либо не соединены. Пусть вершины графа соответствуют городам: красное ребро (пронумеровано 1) соответствует наличию авиалиний, синее ребро (пронумеровано 2) соответствует отсутствию авиалиний. По условию среди трех ребер, соединяющих любые три вершины, одно — красное, второе — синее,

 

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

 

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

Остается  показать, что в графе найдется "пятиугольник", все ребра которого — красные.

Выберем одну из вершин, например  , а красными будут, скажем, ребра 

 

Ребро   не может быть красным, следовательно, красным является одно из ребер: либо  , либо  . Пусть красное  . Если теперь соединить красным ребром вершины   и  , то вершина   должна быть соединена красными ребрами с вершинами, которые принадлежат уже двум красным ребрам. По условию это невозможно. Остается соединить красными ребрами вершины   и  ,   и  . Остальные ребра должны быть синими.

 

Итак, мы получили еще одно свойство.

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

В формулировке свойства 3 можно заменить слово "красный" на "синий" и одновременно слово "синий" на "красный", то есть речь пойдет о пятиугольнике с  синими сторонами и красными диагоналями. Это понятно, поскольку для пятиугольника  и только для него характерно, что  его диагонали образуют также  пятиугольник.

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

 

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

 

Остается  показать, что обязательно найдется еще и второй такой треугольник.

Временно  исключим из рассмотрения одну из его  вершин, скажем  , вместе с ребрами, принадлежащим ей.

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

В противном  случае получается пятиугольник с красными сторонами и синими диагоналями. Теперь восстановим шестую вершину   с ее ребрами.

 

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

Установлено свойство графа, являющееся обобщением свойства 2.

Свойство 4. В любом полном графе с шестью или более вершинами и ребрами одного из двух цветов всегда найдутся два разных треугольника с одноцветными сторонами. Эти два треугольника могут иметь общую вершину или даже общее ребро.

Если два треугольника имеют общую вершину или ребро, то их называют сцепленными.

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

Задача 4. Каждый из семнадцати ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Нужно доказать, что не менее трех ученых переписываются друг с другом по одной и той же теме.

Решение. Условию задачи соответствует полный граф с семнадцатью вершинами и ребрами трех цветов. Из каждой вершины выходит шестнадцать ребер. Докажем, что в таком графе найдется хотя бы один треугольник с одноцветными сторонами. Заметим, что каждая вершина этого графа принадлежит хотя бы шести ребрам одного цвета. Пусть, например, вершина   принадлежит шести красным ребрам.

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

Сформулируем  теперь свойство, доказанное при решении  этой задачи.

Свойство 5. В полном графе с семнадцатью или более вершинами и ребрами трех цветов всегда найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Заметим, что не случайно отношения, которые  были найдены при решении задач, изображавшиеся цветными ребрами, симметричны, если   — друг  , то   — друг  , но не обязательно транзитивны, если   — друг   и   — друг  , то   может и не быть другом  . В случае, когда отношение между объектами было транзитивным, соответствующие ребра образовывали треугольник с одноцветными сторонами.

Задача 5. В работе международного симпозиума лингвистов участвуют   человек. Из любых четырех один может объясняться с остальными тремя хотя бы на одном языке. Нужно доказать, что найдется участник симпозиума, который может объясниться с каждым из остальных участников.

Решение. Имеем полный граф с   вершинами и ребрами двух цветов (синее ребро — двое могут объясниться на каком-нибудь языке, красное — не могут). По условию, среди любых четырех вершин графа всегда найдется, по меньшей мере, одна, синяя степень которой равна трем.

Случай, когда все ребра синие, тривиален, математически неинтересен. Пусть  найдется красное ребро  . Добавим еще какие-нибудь две вершины  . Из четырех вершин   найдется хотя бы одна синяя, степень которой равна трем. Это   или  . Пусть, например, синюю степень три имеет  . Добавим еще одну вершину —  . Из вершин   или   или   имеет синюю степень, равную трем. В обоих случаях   соединена синим ребром с  . Переберем все вершины. В итоге окажется, что   соединена синим ребром со всеми вершинами графа. Во всякой четверке вершин, включая   и  , есть вершина, соединенная синим ребром со всеми остальными вершинами графа. Отсюда, кроме   и  , существует самое большее одна вершина, не соединенная синим ребром со всеми остальными.

Задача о несцепленных треугольниках с одноцветными сторонами

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

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

Решение. Рассмотрим в графе один из треугольников   с одноцветными сторонами. По теореме 3, такой треугольник всегда найдется. Если остальные пять вершин и ребра, соединяющие их попарно, содержат еще один треугольник с одноцветными сторонами, то он и будет являться вторым искомым треугольником. (Для этого случая задача решена.) Если остальные пять вершин   не содержат треугольника с одноцветными сторонами, то они образуют пятиугольник с красными сторонами и синими диагоналями. На рисунке (рис. 1) изображены не все ребра графа, соответствующего задаче, а лишь треугольник   с красными сторонами и пятиугольник   с красными сторонами и синими диагоналями.

 

Покажем, что если какая-нибудь вершина треугольника   соединена синими ребрами с двумя вершинами пятиугольника, через одну, например   с   и   (рис. 2), то найдется еще один треугольник с одноцветными сторонами, не сцепленный с треугольником  .

Действительно, обратим внимание на пятиугольник  . Если он содержит треугольник с одноцветными сторонами, то второй треугольник с одноцветными сторонами, не сцепленный с первым, найден. Если не содержит, то ребра   — красные, поскольку ребра  , по свойству 3 — уже синие. То есть образован треугольник   с красными сторонами, не сцепленный с треугольником   (рис. 3).

Остается  рассмотреть случаи, когда каждая вершина треугольника   соединена красными ребрами, по меньшей мере, с тремя последовательными вершинами пятиугольника  . Тогда у пятиугольника найдутся две вершины, каждая из которых соединена красными ребрами с двумя вершинами треугольника  . На (рис. 4) и (рис. 5) показаны все такие случаи. На (рис. 1.) легко обнаружить два несцепленных треугольника   и  . А на (рис. 5) хотя бы одно из ребер   должно быть красным (иначе вершина   будет соединена синими ребрами с двумя вершинами пятиугольника  , взятыми через одну, а этот случай уже рассмотрен).

 

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

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

 

 

 

Итак, все графы делятся на два  класса: у одних хроматический  индекс равен максимальной степени  вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей. Алгоритм, который можно извлечь из доказательства теоремы 1, за полиномиальное время  находит раскраску в не более  чем   цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.

 

Заключение

Итак, все графы делятся на два  класса: у одних хроматический  индекс равен максимальной степени  вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей. Алгоритм, который можно извлечь из доказательства теоремы 1, за полиномиальное время  находит раскраску в не более  чем   цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.

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

1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.  – М.: Наука, 1990.
2. Зыков А.А. Основы теории графов. – М.: Наука, 1987.
3. Татт У. Теория графов. – М.: Наука, 1988.
4. Харари Ф. Теория графов. – М.: Мир, 1973.
5. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979.