Решение.

Пример.

П. 6. Графы с цветными ребрами.

Решение.

Решим данную задачу с помощью графов. Обозначим вершины графа как a₁, a₂, a₃, b₁, b₂, b₃, где a₁, a₂, a₃ – дома, b₁, b₂, b₃ – колодцы. Между группой вершин a₁, a₂, a₃ и группой вершин b₁, b₂, b₃ наблюдается соответствие. От каждой вершины отходит три ребра к соответствующим вершинам. По условию задачи, мы имеем полный двудольный граф U_3,3 с пересекающимися ребрами. Можно ли построить плоский граф, изоморфный графу U_3,3? Иными словами, является ли граф U_3,3 планарным?

Двудольный граф U_3,3 изображен на рисунке. Из теоремы 7 следует, что данный граф не является планарным. Т.е. проложить непересекающиеся тропинки нельзя!

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

Рассмотрим ситуации, когда одна пара элементов множества находится между собой в одном отношении, другие пары этого же множества – в другом и т. д. Например, 1) среди команд-участников баскетбольного турнира к какому-то моменту могут быть такие, которые уже сыграли матчи друг с другом, и такие, которые не сыграли; 2) существуют страны, установившие между собой дипломатические связи, и страны, между которыми они не установлены.

Для удобства, на диаграммах графов ребра, соответствующие одному отношению, окрашивают в один цвет, а ребра, соответствующие другому отношению – в другой цвет. Чем больше отношений, тем больше приходится вводить цветов для окраски ребер.

Такие графы называют графами с цветными ребрами.

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

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

Примеры других задач:

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

2. Докажите, что во всякой группе из девяти человек, в которой не найдутся трое попарно незнакомых, найдутся четверо попарно знакомых.