МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 13. Графы

Основные понятия

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

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

Задачи

1.

Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

Ответ Решение

Ответ. Нет.

Решение.
Построим граф, вершинами которого являются планеты Солнечной системы, а ребрами — существующие маршруты рейсовых ракет. Изобразив такой граф на рисунке, нетрудно заметить, что он состоит из двух компонент связности (на нашем рисунке они выделены разными цветами). Земля и Марс оказываются в разных компонентах связности, поэтому долететь от Земли до Марса на рейсоых ракетах нельзя.

2.

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

Ответ

Ответ. На рисунке указано одно из возможных решений (клетки пронумерованы в том порядке, в котором их обходит конь).

3.

Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

Ответ Решение

Ответ. Нельзя.

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

4.

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?

Ответ Решение

Ответ. Нет.

Решение.

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

Упражнение: А какие еще компоненты связности есть в этом графе?

5.

В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

Ответ Решение

Ответ. 200.

Решение. Обойдем по очереди все города, считая дороги, входящие из них. Всего таким способом мы насчитаем 400 дорог. Но каждая дорога выходит из двух городов, значит, каждую дорогу мы посчитали два раза. Поэтому на самом деле дорог в государстве в два раза меньше, чем мы насчитали, то есть 200.

Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин.
Докажите эту теорему самостоятельно по аналогии с задачей 5.

6.

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.

Ответ Решение

Ответ. Нет.

Решение. В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.

7.

Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.

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

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

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

8.

В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

Ответ Решение

Ответ. Нет.

Решение. Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.

9.

Школьник Вася Пупкин сказал своему приятелю Вите Иванову:
— У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками...
— Не может этого быть, — сразу же ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?

Решение

Решение. Решение этой задачи полностью аналогично решению задачи 6.

10.

У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ Решение

Ответ. Нет.

Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.

11.

Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Ответ Решение

Ответ. Нет.

Решение. Сделаем города вершинами графа, а дороги — его ребрами. По условию в этом графе 100 ребер, а по теореме 1 число ребер равно половине суммы степеней всех вершин. Значит, сумма степеней всех вершин равна 200. Но степень каждой вершины по условию равна 3, а 200 не делится на 3. Полученное противоречие доказывает, что такого быть не может.

12.

В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.

Решение

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

13.

Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Решение

Решение. Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия — его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными.) Люди, сделавшие нечетное число рукопожатий, — нечетные вершины такого графа, поэтому по теореме 2 их количество четно.

14*.

Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4 и 2 соответственно.

Решение

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

15*.

Можно ли расположить в пространстве 9 шаров так, чтобы каждый из них касался ровно пяти других?

Ответ Решение

Ответ. Нет.

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

16*.

а)

Можно ли нарисовать на плоскости 8 отрезков так, чтобы каждый пересекался ровно с тремя другими?

б)

Тот же вопрос для 9 отрезков.

Ответ Решение

Ответ. а) Да, см. рисунок; б) нет.

Решение. Сделаем отрезки вершинами графа и соединим ребрами те из них, которые пересекаются между собой. По условию п. б) в таком графе нечетное число нечетных вершин, что противоречит теореме 2. Для пункта а) это рассуждение не годится, однако это еще не означает, что сделать такой рисунок возможно. Чтобы это доказать, надо его нарисовать. Для этого достаточно придумать рисунок с 4 отрезками, каждый из которых пересекается ровно с тремя другими, а потом изобразить два таких рисунка рядом. (Здесь важно, что в условии фигурируют именно отрезки, а не прямые.)