проект по дискретке (2)

1. Анализ графавой модели

Петриченко Никита
Романов Иван

2. В качестве основы, мы взяли карту страны ( Польша )

Карта Польши была взята с сайта:
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE
%D0%BB%D1%8C%D1%88%D0%B0\
Графавая модель сделана Никитой
Петриченко в Figma.

3. Диаграмма

4.

5. Находим кротчайший маршрут из точки : P в точку : C

В результате рассмотрения графа алгоритмом Дейкстеры обнаружилось,
что вершины P и C соединены двумя кратчайшими путями, наиболее
благоприятным из которых оказался:
Кратчайшие пути к узлам графа :
Путь: P-R-S-B-C
P-O | 3
P-R | 4
P-O-N | 6
P-O-N-M | 8
P-O-N-M-K | 13
P-R-S | 13
P-R-S-B | 20
P-O-N-M-K-L | 19
P-O-N-M-K-L-F | 24
P-O-N-M-K-L-F-E | 25
P-O-N-M-K-L-F-E-D | 28

6.

7. Алгоритм прима :

8.

9.

10.

Минимальный суммарный вес=73

11.

Обход графа в глубину :

12.

13.

14.

Граф был пройден за 15 шагов

15.

Обход графа в ширину от точки P

16.

Граф был пройден в ширину от
точки P за 8 шагов.
Вывод: обход в ширину
оказался эффективнее чем в
глубину [8 шагов (в ширину) <
15 шагов ( в глубину ) ]

17.

Задача инспекции дорог :
Длинна оптимального пути почтальона составит
сумму всех ребер графа +6 потому что его путь будет
проходить дважды через M-L
3+3+2+6+4+6+6+5+4=39
P-O-N-M-L-K-M-L-RP

18.

Задача коммивояжера
I-G-H-A-J-I
(5+6+4+5+6=26)
J-A-H-G-I-J
(5+4+6+5+6=26)
A-J-H-G-I-A
(5+4+6+5+12=32)
H-A-J-I-G-H
(4+5+6+5+6=26)
G-I-J-A-H-G
(5+6+5+4+6=26)
Наименьшая верхняя
граница = 26

19.

Наибольшая из найденных
нижних границ 26

20.

Над проектом работали
Петриченко Никита
Романов Иван