Рис. 3.7. Ориентированный граф

↑

⇐ ПредыдущаяСтр 5 из 6Следующая ⇒

Рис. 3.7. Ориентированный граф

Составим матрицу смежности, соответствующую данному ориентированному графу:

По матрице смежности построим полное дерево перебора решений — рисунок 3.8.

Рис. 3.8. Полное дерево перебора решений

На рисунке 3.8 видно, что кратчайший путь из вершины А в вершину F равен 17 и имеет вид A-B-E-F.

Пример 4. На рисунке 3.9 представлена схема дорог, связывающих города А, Б, С, D, Е, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город G?

Рис. 3.9. Схема дорог.

Существует несколько способов решения этой задачи. Рассмотрим их.

Вариант 1. По графу можно построить матрицу смежности, а на её основе построить дерево, корнем которого будет служить вершина А. Число листьев построенного дерева будет равно числу дорог из города А в город G.

Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.

Вариант 2. Пусть Кх — число путей из города А в город X.

Начнем считать число путей с конца маршрута. Так как в город G есть дороги из городов С, E, F, то K_G = К_C + К_Е + K_F.

В свою очередь К_C = 1 + K_D = 1 + 1 = 2, К_Е = К_B + K_C =1 + 2 = 3, К_F = K_C = 2.

Таким образом, K_G = 2 + 3 + 2 = 7.

Вариант 3. Можно считать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 3.10.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология