О графах с цветными ребрами

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

Действительно, граф с цветными ребрами можно задавать таблицей с n строками и n столбцами, где n - число вершин. Для этого нужно занумеровать вершины, и на пересечении i-й строки и j-го столбца таблицы написать цвет ребра, соединяющего i-ю и j-ю вершины. Легко сообразить, что можно занумеровать вершины графов на рисунках 1а, б и в так, что таблицы окажутся одинаковыми. Именно поэтому мы и говорим, что это - один и тот же граф.

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

Применение графов с цветными ребрами упрощает решения некоторых задач и делает их более наглядными.

Перейдем теперь к решению задач.

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

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

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

Задача полностью решена. Кроме того, при ее решении доказаны два свойства.

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

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

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

1. Каждый город соединен авиалиниями с двумя и только с двумя другими городами.

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

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

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

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

Теперь выберем одну из вершин, например A, а красными будут, скажем, ребра АВ и АС (рис. 5). Ребро СВ не может быть красным, следовательно, красным является одно из ребер либо CD, либо CE. Пусть красное - CD. Если теперь соединить красным ребром вершины B и D, то вершина E должна быть соединена красными ребрами с вершинами, которые принадлежат уже двум красным ребрам. По условию это невозможно. Остается соединить красными ребрами вершины D и E, B и E. Остальные ребра должны быть синими (рис. 1а).

Вместе с решением задачи получено еще одно свойство графа.

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

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

Решение. Пусть у графа с шестью вершинами A, B, C, D, E, F красные ребра соответствуют парам абонентов, которые говорили друг с другом по телефону, синие - тем, кто не говорил. Тогда найдется хотя бы один треугольник с одноцветными сторонами, например, треугольник ABF с красными сторонами. Временно исключим из рассмотрения одну из его вершин, скажем A, вместе с выходящими из нее ребрами. Найдется ли в оставшемся графе с пятью вершинами треугольник с одноцветными сторонами? Если найдется, то он содержится и в исходном графе. В противном случае получаем пятиугольник с красными сторонами и синими диагоналями (рис. 6). Теперь восстановим шестую вершину A с ее ребрами. Ребра AF и AB - красные. Если ребро AE или AC будет тоже красным, то образуется еще хотя бы один треугольник с красными сторонами AEF или ABC. Если оба эти ребра будут синего цвета, то появится треугольник АСЕ с синими сторонами.

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

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

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

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

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

Решение. Рассмотрим в графе один из треугольников, например KLM, с одноцветными сторонами. Если остальные пять вершин и ребра, соединяющие их попарно, содержат треугольник с одноцветными сторонами, то он и будет являться вторым искомым треугольником. Если остальные пять вершин A, B, C, D, E не содержат треугольника с одноцветными сторонами, то они образуют пятиугольник с красными сторонами и синими диагоналями (свойство 3). На рисунке 7 изображены не все ребра графа, а лишь треугольник KLM с красными сторонами и пятиугольник ABCDE с красными сторонами и синими диагоналями. Покажем, что если какая-нибудь вершина треугольника KLM соединена синими ребрами с двумя вершинами пятиугольника, взятыми через одну, например, K с A и C (рис. 8), то найдется еще один треугольник с одноцветными сторонами, не сцепленный с треугольником АСК. Действительно, посмотрим на пятиугольник BDELM. Ясно, что невозможно окрасить ребра BL и ВМ так, чтобы он превратился в пятиугольник с красными сторонами и синими диагоналями. Поэтому он обязательно содержит одноцветный треугольник, не сцепленный с треугольником АСК (рис. 9).

Остается рассмотреть случай, когда каждая вершина треугольника KLM соединена красными ребрами по меньшей мере с тремя последовательными вершинами пятиугольника ABCDE. Пусть, например, вершина K соединена красными ребрами с вершинами A, B и C. Тогда вершины L и M соединены красными ребрами с A, B и C. В противном случае найдутся два несцепленных треугольника с вершинами K, L или M и основаниями - сторонами пятиугольника ABCDE. Но тогда (см. рис. 10) мы находим два треугольника CLM и АВК с красными сторонами. Таким образом, во всех случаях найдутся два несцепленных треугольника с одноцветными сторонами.

Решим теперь задачу, предложенную на Шестой международной математической олимпиаде.

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

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

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

Л. Ю. Березина

Ответы и решения