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

Кружок 9-10 класса

Листок 5. Графы

1.

Верно ли, что среди любых а) пяти, б) шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых?

2.

Пусть данный граф можно обойти, побывав на каждом ребре ровно по одному разу. Чему может быть равно количество вершин, из которых исходит нечётное число рёбер? Определение. Граф называется двудольным, если его вершины можно раскрасить в два цвета так, чтобы каждое ребро имело разноцветные концы.

3.

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

4.

В каждой строчке и каждом столбце доски 8×8 стоит по две фишки. Докажите, что их можно раскрасить в два цвета так, чтобы в каждом столбце и в каждой строчке фишки были раскрашены в разные цвета.

5.

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

6.

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

7.

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

8.

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

9.

Есть три домика и три колодца. Можно ли соединить каждый домик с каждым колодцем тропинкой так, чтобы тропинки не пересекались?