В рассматриваемом графе количество вершин N=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)