МинимальноеH остовное дерево
150 км A
20 км |
|
34 |
км |
1. DH (20 кмD) 2500 |
1500 км |
км |
|
|
C |
Шага и ребра
H
20 км |
150 кмA |
|
34 км |
||
D |
||
|
1500 км |
|
2500 км |
||
1. DH (20 км) |
C |
|
2. DA (34 км) |
||
Условная оптимизация
H
150 кмA
20 км
D 34 км 1500 км
|
2500 км |
|
1. |
DH (20 км) |
C |
2. |
DA (34 км) |
|
3. |
АС (1500 км) |
|
Условная оптимизация |
||
|
H |
|
|
S |
|
|
150 кмA |
|
|
20 км |
|
|
D 34 км |
1500 км |
|
|
|
Ответ: |
2500 км |
|
1.DH (20 км)
2.DA (34 км)
3.АС (1500 км)
C
Суммарная длина … =1554 км
Построить мин. остовное дерево |
||||||||||
|
жадным алгоритмомЕ |
|
|
|
||||||
|
|
|
|
|
|
S |
4 |
|
|
|
|
|
|
|
|
1 |
3 S |
|
|
||
|
|
|
|
|
8.5 |
|
|
|||
|
|
|
|
|
G |
I |
S |
D |
О |
|
|
|
СПб |
|
|
|
2 |
9 |
|
|
Ответ: |
|
|
|
|
|
|
8 |
7 |
|
||
|
|
|
|
|
|
|
минимальное остовное |
|||
|
|
|
12 b |
|
5 |
|
S |
|
||
|
b 2 |
d b |
|
7 |
Н |
|
|
дерево |
||
|
|
С |
|
|
||||||
|
10-b |
|
10 |
|
1. GE ( 1 км) |
|||||
|
|
Москва |
|
21S 8 |
|
S |
|
2. GI ( 2 км) |
||
|
|
a |
|
|
Екатеринбург |
|
|
|
|
|
Рига |
|
12+a |
|
А |
14 |
M |
|
3. EO ( 4 км) |
||
|
|
11 35 |
|
|
4. GС ( 5 км) |
|||||
|
|
|
|
d-1 |
38 |
|
|
|||
|
|
|
|
|
|
5. DН ( 7 км) |
||||
|
|
|
|
c+5 |
В |
37 |
|
|||
|
|
|
|
|
|
|||||
b |
1 |
13-b |
|
|
|
43 |
20 |
|
6. НС ( 7 км) |
|
|
|
L |
|
7. МС ( 8 км) |
||||||
|
|
|
39 |
|
|
|
||||
|
|
|
Aстрахань |
|
K |
|
8. LA ( 11 км) |
|||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
9. AM ( 14 км) |
|||
|
|
|
|7-d| |
|
|
|
|
|
|
|
|
|
Одесса |
|
|
|
|
|
10. ВК ( 20 км) |
||
|
|
|
|
|
|
|
|
|
11. МК ( 37 км) |
|
|
|
|
n=12 |
|
|
|
|
протяженность: 116 |
||
|
|
|
|
|
|
|
км |
|
||
|
|
|
|
|
|
|
|
|
||
|
|
|
Число шагов =12-1 |
|
(n-1) |
|
|
|||
b
+a
b Задание и пример
|
|
|
|
|
|
|
|
|
|
Е |
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
4 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
3 S |
|
|
|
||
|
|
|
|
|
|
|
|
8.5 |
|
|
|
|||
|
|
|
|
|
|
|
G |
|
I |
S |
D |
О |
|
|
|
|
|
|
|
|
|
|
|
2 |
9 |
|
|
Ответ: |
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
S |
7 |
|
минимальное остовное |
|
|
|
|
-а-b |
|
|
Уренгой |
|
7 |
Н |
|
|
дерево |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
СПб |
|
23 |
|
|
С |
|
|
10 |
|
1. GE ( |
1 км) |
|||
|
|
|
|
|
1 |
|
|
|
|
|||||
|
|
|
|
|
|
2 |
21 |
|
|
|
S |
|
2. GI ( |
2 км) |
b 1 |
|
d b |
16 b |
|
с |
S |
8 |
|
|
|
||||
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
|
Рига |
a |
Москва 10-bЕкатеринбург |
А |
|
14 |
M |
|
3. EO ( |
4 км) |
|||||
|
|
|
|
|
|
|
|
|
|
|
4. GС ( 5 км) |
|||
|
|
12+a |
|
с + |
5 |
11 |
45 |
38 |
|
|
||||
|
|
|7-d| |
|
|
|
|
5. DН ( 7 км) |
|||||||
|
|
|
|
|
|
|
|
|||||||
|
|
b |
|
|
|
В |
|
|
||||||
|
|
2 |
|
|
|
|
|
|
|
|
||||
b 2 |
|
- |
|
|
|
|
|
37 |
|
|
|
|||
1 |
Aстрахань |
|
|
|
6. НС ( 7 км) |
|||||||||
|
|
|
|
43 |
|
|
|
|||||||
|
|
|
d |
|
|
|
|
|
20 |
|
||||
|
Одесса |
|
|
|
L |
|
|
7. МС ( 8 км) |
||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
39 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
K |
|
8. LA ( |
11 км) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
9. AM ( 14 км) |
|
|
|
|
|
|
|
|
|
|
|
|
|
10. ВК ( 20 км) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
11. МК ( 37 км) |
|
|
|
|
|
|
|
n=12 |
|
|
|
|
протяженность: 116 |
|||
|
|
|
|
|
|
|
|
|
|
км |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
Число шагов =12-1 |
|
|
(n-1) |
|
|
|
||
