Раскраска ребер графа

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

 

Ясно, что если наибольшая из степеней вершин графа   равна  , то  . Следующий результат, известный как теорема Визинга, дает точные оценки для хроматического класса графа  . Доказательство этой теоремы можно найти у Оре (Ore O. The four-color problem, Academic Press, New York, 1967).

Теорема 7.1.(Визинг, 1964) Пусть в графе  , не имеющем петель, наибольшая из степеней вершин равна   тогда  .

Задача, состоящая  в выяснении того, какие графы  имеют хроматический класс  , а какие  , не решена. Однако в некоторых частных случаях соответствующие результаты находятся легко. Например,   или 3 в зависимости от того, четно   или нечетно, а  , при  . Хроматические классы полных графов и полных двудольных графов вычисляются тоже просто.

Теорема 7.2.  .

Доказательство

Без потери общности можно считать, что   и что граф   изображен так:

 

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

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

Теорема 7.3.  , если   нечетно  , и  , если   четно.

Доказательство

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

 

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

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

 

Задачи  на графы с цветными ребрами и вытекающие из них свойства

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

Свойства  полных графов с цветными ребрами

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

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

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

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

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

 

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

 

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

 

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

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

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

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

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

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

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

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

 

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

 

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

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

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

 

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

 

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

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

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

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

 

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

 

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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