СКМ 5-7
(24.01.2013 – 31.01.2013)
Лист № 3
1. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
2. Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным.
3. 
* В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелетов; б) 196 перелетов.
4. Можно ли составить решетку, изображенную на рисунке
а) из 5 ломаных длины 8?
б) из 8 ломаных длины 5? (длина стороны клетки равна 1).
5. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
6. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата, так, что квадрат разбился на треугольники. Сколько получилось треугольников?
