Элементы теории графов. Сюсюкалов А.И - 17 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

12
2.2. Задачи
1. Схема мостов города Кёнигс-
берга изображена на рис. 9. Можно ли
совершить прогулку, пройдя по каж-
дому мосту ровно один раз?
2. Можно ли нарисовать граф, изображённый а) на рисунке
10, а; б) на рисунке 10, б, не
отрывая карандаша от бума-
ги и проводя каждое ребро
ровно один раз?
3. Можно ли прогуляться по парку и его окре-
стностям (рис. 11) так, чтобы при этом перелезть
через каждый забор ровно один раз?
4. а) Дан кусок проволоки длиной 120 см.
Можно ли, не ломая проволоки, изготовить каркас куба с реб-
ром 10 см? б) Какое наименьшее число раз придётся ломать
проволоку, чтобы всё же изготовить требуемый каркас?
5. Докажите, что связный граф с
n2
нечётными вершинами
можно нарисовать, оторвав карандаш от бумаги ровно
1
n
раз
и не проводя никакое ребро дважды.
6. Можно ли, не отрывая карандаша от бумаги и не проводя
по одной линии дважды, нарисовать: а) квадрат с диагоналями;
б) правильный пятиугольник с диагоналями?
7. Турист обошёл 6 улиц одного города, пройдя каждую
ровно два раза, но не смог обойти их, пройдя каждую по одному
разу. Могло ли так быть, если а) улицы могут оканчиваться ту-
пиком; б) конец каждой улицы – перекрёсток?

Страницы