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

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

Графы – 2. 17 ноября 2012

1.

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

2.

Художник-авангардист нарисовал картину "Контур квадрата и его диагонали". Мог ли он нарисовать свою картину не отрывая карандаша от бумаги и не проводя одну линию дважды?

3.

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

4.

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

5.

Имеется кусок проволоки длиной 120см. Можно ли, не ломая его, сделать из него каркас куба со стороной 10см? И если нельзя, то в скольких местах придётся эту проволоку сломать?

6.

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

7.

Может ли ладья обойти шахматную доску, сделав каждый из возможных ходов ровно один раз? (например, должны быть сделаны ходы а1-а2, а1-а3, … а1-а8, а1-b1, а1-c1, … a1-h1 и т. д. для остальных клеток).

Дополнительные задачи:

8.

Решите задачу 7 для коня и ферзя. Путь в графе – последовательность ребер, в которой конец каждого ребра (кроме последнего) совпадает с началом следующего.

9.

а)

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

б)

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