5 - Задачи на графы

1. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

2. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в F.

4. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из B в D.

5. На рисунке приведена весовая матрица графа. Определите вес ребра, соединяющего вершины B и D.

6. На рисунке приведена весовая матрица графа. Определите вес ребра, соединяющего вершины C и E.

7. На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами. Определите длину маршрута A-B-D-E.

8. На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами. Определите длину маршрута D-B-E-C-A.

9. На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами. Определите длину маршрута E-A-C-D-B.

10. На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами. Определите длину маршрута E-B-D-C.