Составители:
Рубрика:
79
134.
Из города А в город В ведут несколько дорог (карта дорог на рисунке). Найдите число
маршрутов из А в В, учитывая, что при движении необходимо всегда приближаться к В.
135.
Может ли в ориентированном графе полустепень захода каждой вершины быть равна
3, а полустепень исхода – 4?
136.
В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и
столица) соединены дорогами с односторонним движением. Из каждого нестоличного
города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в
столицу нельзя проехать ни из одного города.
137.
В некотором государстве 101 город. а) Каждый город соединен с каждым дорогой с
односторонним движением, причем в каждый город входит 50 дорог и из каждого города
выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой,
проехав не более чем по двум дорогам; б) Некоторые города соединены дорогами с
односторонним движением
, причем в каждый город входит 40 дорог и из каждого города
выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого,
проехав не более чем по трем дорогам
138.
В стране Ориентация на всех дорогах введено одностороннее движение, причем из
любого города в любой другой можно добраться, проехав не более чем по двум дорогам.
Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться
до каждого. Докажите, что для любых двух городов это можно сделать, проехав
не более,
чем по трем дорогам.
139.
Найдите компоненты сильной связности графа, заданного матрицей смежности:
1 2 3 4 5 6 7 8 9
1 0 1 1 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 1 0 1 0 0 0 0 0
4 0 0 0 0 1 0 0 0 0
5 0 0 0 0 0 1 0 0 0
6 0 0 0 0 0 0 1 0 0
7 0 0 0 1 0 0 0 0 0
8 0 0 1 0 0 0 0 0 0
9 1 0 0 0 0 0 0 1 0
140. Найдите компоненты сильной связности графа:
А В
2
5
1
4
3
Страницы
- « первая
- ‹ предыдущая
- …
- 77
- 78
- 79
- 80
- 81
- …
- следующая ›
- последняя »
