Составители:
Рубрика:
74
103.
Найдите цикломатическое число для графов:
· К
n
;
· К
m,n
;
· W
n
;
· графа Петерсона;
· любого связного регулярного графа с n вершинами степени регулярности r.
104. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое
наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было
проехать в каждый?
105.
В несвязном графе с 5 компонентами связности любое ребро является мостом. Сколько
вершин в графе, если ребер 115? (1 балл)
106.
Постройте остовы графа, изображенного на рисунке методами поиска в ширину и в глубину.
107.
Найдите какие-нибудь остовные деревья для графов К
5
, К
33
, и в графе Петерсона.
108.
Найти минимальный каркас графа, изображенного на рисунке, используя алгоритм Краскала.
109.
Постройте каркас минимального веса для графа заданного матрицей весов (2 балла)
0 20
∞ ∞ ∞
15
∞
20 0
∞ ∞
1
∞
3
∞ ∞
0 5 2
∞
2
∞ ∞
5 0 3
∞
1
∞
1 2 3 0 10
∞
15
∞ ∞ ∞
10 0
∞
∞
3 2 1
∞ ∞
0
0 2
∞ ∞ ∞
7 10
2 0 10
∞ ∞
1 0
∞
10 0 2
∞ ∞ ∞
∞ ∞
2 0 5 1
∞
∞ ∞ ∞
5 0 3
∞
7 1
∞
1 3 0 2
10
∞ ∞ ∞ ∞
2 0
0
∞ ∞ ∞ ∞
3 2
∞
0 10
∞ ∞
4
∞
∞
10 0
∞ ∞
4
∞
∞ ∞ ∞
0 2 3
∞
∞ ∞ ∞
2 0 1
∞
3 4 4 3 1 0 1
2
∞ ∞ ∞ ∞
1 0
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
