Двусторонние дороги
12. В системе двусторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.
13. Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз.
14. Задана система двусторонних дорог. Найти замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз.
15. Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна.
16. По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого из остальных городов, проезжая не более 100 км.
17. По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B.
18. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Определить N-периферию для заданного N.
19. В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города A в город B с минимальной величиной S+P, где S - сумма длин дорог пути, а P - сумма пошлин проезжаемых дорог.
20. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города A в город B ( ко-торый может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.
21. Система двусторонних дорог называется трисвязной , если для любой четверки разных городов A,B,C,D существует два различных пути из A в D, причем один из них проходит через B, а другой - через C. Определить, является ли трисвязной данная система двусторонних дорог.
| Оглавление | Вперед |
| Каталог | Индекс раздела |
