Инф Мен 5 задание

1. Поиск структуры с оптимальной стоимостью

2. Задача:

Телекоммуникационная компания Феникс-Комьюникейшн планирует
внедрять сеть по инновационной технологии 10G.
Для первого шага инновационного проекта необходимо соединить города
одного региона, проведя магистральные квантовые сети между
крупнейшими его городами. Построение сети по новой технологии –
чрезвычайно дорогостоящее мероприятие, которое требует минимизации
затрат.
Карта региона представлена в виде графа, вершины которого являются
городами, а ребра показывают стоимость проведения сети между
городами.
Задача – соединить все города в сеть, минимизируя стоимость
строительных работ.

3. Задача построения остовного дерева

Допустим, есть n городов, которые
необходимо соединить дорогами, так,
чтобы можно было добраться из любого
города в любой другой (напрямую или
через другие города). Разрешается
строить дороги между заданными парами
городов
и
известна
стоимость
строительства каждой такой дороги.
Требуется решить, какие именно дороги
нужно строить, чтобы минимизировать
общую стоимость строительства.

4. Алгоритм Крускала

Выписать в таблицу множество вершин графа.
Найти ребро с минимальным весом. Включить его вершины в
множество.
Перейти к следующему ребру минимального веса. Если оно не
образует цикл – включить его вершины в множество (новое или уже
существующее). В противном случае – исключить ребро.
Продолжать действия до тех пор, пока все вершины не будут в одном
множестве.
Ребро
Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6}
(V2,V3)
1
{V2,V3},{V1},{V4},{V5},{V6}
Вкл.
(V4,V6)
1
{V2,V3},{V4,V6},{V1},{V5}
Вкл.
(V1,V4)
2
{V2,V3},{V1,V4,V6},{V5}
Вкл.
(V3,V4)
2
{V1,V2,V3,V4,V6},{V5}
Вкл.
(V2,V4)
2
(V3,V5)
3
Искл.
{V1,V2,V3,V4,V5,V6}
Вкл.

5.

Ребро Вес
Множества вершин
10
Операция
6
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
9
5
5
4
3
2
3
7
6
8
3
5
10
11

6. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
6
10
4
5
7
5
10
8
9
5
4
3
6
Вариант 1

7. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
12
3
7
7
3
9
10
5
8
8
10
5
11
Вариант 2

8. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
9
6
6
4
7
10
12
5
3
2
9
10
4
Вариант 3

9. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
11
5
4
8
2
3
7
7
5
3
8
3
11
Вариант 4

10. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
2
8
3
5
5
12
10
9
8
5
2
4
3
Вариант 5

11. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
5
6
12
8
3
4
7
11
9
4
6
8
5
Вариант 6

12. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
9
8
7
6
4
10
7
7
8
10
3
5
9
Вариант 7

13. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
6
10
4
5
7
5
10
8
9
5
4
3
6
Вариант 8

14. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
12
3
7
7
3
9
10
5
8
8
10
5
11
Вариант 9

15. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
9
6
6
4
7
10
12
5
3
2
9
10
4
Вариант 10

16. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
11
5
4
8
2
3
7
7
5
3
8
3
11
Вариант 11

17. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
2
8
3
5
5
12
10
9
8
5
2
4
3
Вариант 12

18. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
5
6
12
8
3
4
7
11
9
4
6
8
5
Вариант 13

19. Карта региона представлена в виде графа, вершины которого являются городами, а ребра показывают стоимость проведения сети между

городами.
Задача – соединить все города в сеть, минимизирую стоимость строительных работ.
Ребро Вес
Множества вершин
Операция
{V1},{V2},{V3},{V4},{V5},{V6},{V7},{V8},{V9}
9
8
7
6
4
10
7
7
8
10
3
5
9
Вариант 14