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

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

Занятие 8 (26 ноября 2016 года). Графы 3

1.

Расставьте в кружочках на рисунке 1 числа от 1 до 6 (каждую ровно один раз), чтобы никакие два соседних числа не стояли в кружочках, соединённых отрезком.

Рисунок 1	Рисунок 2	Рисунок 3

2.

Отметьте на плоскости а) 6 точек; б) 8 точек и соедините их прямолинейными отрезками таким образом, чтобы из каждой точки выходили ровно 3 отрезка, чтобы отрезки не пересекались и чтобы из каждой точки, следуя по отрезкам, можно было бы добраться до любой другой.

3.

Диагональю многоугольника называется отрезок, соединяющий две его несоседние вершины. Сколько диагоналей в а) в шестиугольнике? б) в 100-угольнике?

4.

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

5.

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

6.

Известно, что в стране ровно 40 дорог, каждая дорога соединяет ровно два города (тупиков и развилок нет), две разные дороги не могут соединять одну и ту же пару городов. Кроме того, известно, что нет города, в который не ведёт ни одной дороги.

а)

Какое наибольшее число городов может быть в этой стране?

б)

А какое наименьшее?

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

7.

Отметьте на плоскости 12 точек и соедините их отрезками так, чтобы из каждой точки выходили ровно 5 отрезков и чтобы отрезки не пересекались.

8.

В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трём авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из каждого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?

9.

Докажите, что не существует многогранника, у которого было бы ровно семь рёбер.