3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?
Ответ. Нет (теорема о четности числа нечетных вершин).
5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей?
Ответ. Нет, не может.
6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 =>Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.
7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
|
|
Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.
Связность.
8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.
Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.
Графы Эйлера.
9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист
а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?
10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?