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

Квант 1973, №8 с. 49-52 Тег UQTC

О графах
с цветными ребрами
Л. Ю. Березина

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

В этой статье рассматривается только такие графы, у которых каждую

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

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

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

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

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

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

Рис. 1a. Рис. 16. Рис. 1в.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 4. Изозем группу лодей «одноородной», если любые два целевка из этой группы знакомы, или,

Рис. 8. Напротив, не знакомы. Доказите, что среди восмы случайно встретились людей всегда найдуmsя две однородные группы, состоящие из трех человек каждой, причем никак из первой группы не входит во вторую.

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

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

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

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

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

Решение. Условия задачи соответствует граф с семнадцатью вершинами и ребрами точек цветов.