В рассматриваемом графе количество вершин N=7
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
В рассматриваемом графе количество вершин N=7, следовательно, матрица длин дуг ориентированного графа D Будет иметь размерность 7×7
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.di = min(j) dij
i j 1 2 3 4 5 6 7 di
1 V1 3 6 0 0 9 0 0
2 0 V2 2 5 0 0 0 0
3 0 0 V3 0 0 0 7 0
4 0 0 0 V4 1 0 0 0
5 0 0 0 0 V5 0 4 0
6 0 0 0 0 0 V6 4 0
7 0 0 0 0 0 0 V7 0
Требуется найти кратчайший путь из вершины V1 в вершину V7
Инициализируем граф, для этого начальной вершине графа присвоим значение нуля.Оставшимся вершинам – бесконечно большое число ∞.
(1,2) (1,3) (1,7) (2,3) (2,4) (3,4) (3,6) (3,7) (4,5) (5,6)
Первая итерация
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
В результате при расчёте наилучший путь с помощью алгоритма Беллмана -Форда найден и равен 9, то есть:
1-2-3-4-6-7
Нужно полное решение этой работы?
Решение
В рассматриваемом графе количество вершин N=7, следовательно, матрица длин дуг ориентированного графа D Будет иметь размерность 7×7
i j 1 2 3 4 5 6 7 di
1 V1 5 0 6 0 9 0 0
2 0 V2 4 2 0 0 0 0
3 0 0 V3 2 3 0 0 0
4 0 0 1 V4 0 5 6 0
5 0 0 0 0 V5 0 1 0
6 0 0 0 0 0 V6 1 0
7 0 0 0 0 0 0 V7 0
Требуется найти кратчайший путь из вершины V1 в вершину V7
(1,2) (1,4) (1,6) (2,3) (2,4) (3,5) (4,6) (4,7) (5,7) (6,7)
Таблица 1 - Анализ по продолжительности пути.
Путь
(i,j) Количество предшествующих
Путей. Продолжительность
пути Точка
начала
пути Продолжительность
минмального пути,
min.
(1,2) 0 5 0 5
(1,4) 0 6 0 6
(1,6) 0 9 0 9
(2,3) 1 4 5 9
(2,4) 1 2 5 7
(3,4) 1 2 9 11
(3,5) 1 3 9 12
(4,3) 3 1 11 12
(4,6) 3 5 11 16
(4,7) 3 6 11 17
(5,7) 1 1 12 13
(6,7) 2 6 16 22
Продолжительность минмального пути : (1,4)(4,3)(3,5)(5,7) =13
П.3
. №15.Алгоритмы поиска путей в графе и поиска минимального пути в орграфе.
3823715127805Применив алгоритм Терри, найти путь из вершины 1 в вершину 14 графа G.
а) на «развилке» выбирать путь влево;
б) на «развилке» выбирать путь вправо;
в) на «развилке» выбирать путь прямо.
Минимальный путь из вершины A в E в орграфе, заданном таблицей 1.=4
Минимальный путь из вершины A в F в орграфе, заданном таблицей 1.=2
Граф содержит Эйлеров цикл. Граф содержит Эйлерову цепь:
Граф содержит Гамильтонову цепь:
Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу 1-2-3-4.
Матрица смежности..
Расстояние между вершинами 4: 0⇒2⇒3
Расстояние между вершинами 1: 0⇒2
Расстояние между вершинами 3: 1⇒2
Расстояние между вершинами 1: 3⇒1
Матрица смежности.
Расстояние между вершинами 6: 0⇒3⇒1
Расстояние между вершинами 3: 1⇒0
Расстояние между вершинами 1: 1⇒2
Расстояние между вершинами 2: 2⇒1
Расстояние между вершинами 5: 2⇒1⇒3
Радуис граф: 7 (3⇒7)
Заказать работу
на новый заказ в Автор24.
