О графах с цветными ребрами (ответы и решения)

1. Пусть красное ребро означает, что два делегата могут объясниться на одном языке, а синее - что не могут. Если красного треугольника нет, то по свойству 2 должен быть треугольник с синими сторонами. Но это противоречит условию.

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

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

Предположим, что нет красного треугольника. Пусть какая-нибудь вершина A соединена красными ребрами с B1, B2, B3 и B4, синими - с C1, C2, C3 и C4. Ребра вида BiBj - синие (рис. 1). Каждая из Bi соединена тремя красными ребрами с вершинами Cj, Два красных ребра связывают вершины вида C между собой (поскольку красных ребер BiCj - двенадцать). Пусть Bi связана красными ребрами с C1 C2, и C3. Между собой C1 C2, и C3 соединены синими ребрами, иначе образовался бы треугольник с красными сторонами (рис. 2).

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

Тогда C4 принадлежит двум красным ребрам вида. C4Ci, например, C4C3 и C4C2. Но C4 принадлежит еще двум красным ребрам. Одно из них, - например, C4B2 (рис. 3). Хотя бы одно из ребер B2C2 и B2C3 - тоже красное, то есть хотя бы один из треугольников B2C3C4 и B2C2C4 имеет красные стороны.

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

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

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

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

Рассмотрим некоторое красное ребро АВ. Пусть синяя степень вершины A равна k.

Предположим, что k >= n/2. Легко видеть, что B соединена красными ребрами с теми вершинами, с которыми A соединена синими ребрами. Поэтому, если красная степень вершины B равна l, то l = k + 1 > k >= n/2.

5. Каждому жителю поставим в соответствие вершину графа. Пусть синее ребро означает, что двое дружат, а красное - что не дружат. Получим граф с n вершинами и ребрами двух цветов, который можно подвергать следующим преобразованиям: выбирать вершину и все красные ребра, которым она принадлежит, перекрашивать в синие, а все синие - в красные. По условию, каждый треугольник может стать синим, то есть в графе могут быть только или треугольники с синими сторонами, или треугольники, у которых одна сторона - синяя и две - красные. (Докажите, что при преобразованиях это свойство графа не меняется.)

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

Новости игр и головоломок

Пройдите лабиринты на флеш

24.09.2016 Лабиринты разных размеров.

Слова, слова, слова...

09.09.2016 Словесно-интеллектуальный конкурс № 73.

Вот тебе бог, а вот тебе и пророк!

02.09.2016 Литературная викторина № 72.

Новые стихи-каламбуры.

07.07.2016 Не хуже "королей рифмы".

Слова, в словах:

07.07.2016 добавлены слова, разбивающиеся на слова.

Добавлены загадки с метаграммами.

05.07.2016 Шарадные загадки и пародии на них.

Слова, в словах:

04.07.2016 примеры, список слов, в которых прячутся другие слова.

Пополнение вопросов ребром, а также

30.06.2016 вопросы учёного, возникшие утром 1-го января.

Статья о метаграммах.

17.06.2016 Метаграмма - примеры, список метаграмм и добавлялок-вставлялок.

Бессистемное программирование.

09.04.2016 Пример программы для ассемблера FASM.