Графы

Проверка ранее изученного материала

Задание 1

На ри­сун­ке изображена схема дорога, свя­зы­ва­ю­щих города A, B, C, D, E, F, G, H, K, L, M. По каж­дой дороге можно дви­гать­ся только в одном направлении, ука­зан­ном стрелкой. Сколь­ко существует раз­лич­ных путей из го­ро­да A в город M, причем не проходящих через город К?

Задание 2

На схеме, в виде графа, изображены дороги между городами. В таблице указана протяженность между ними. Схема и таблица рисовались независимо друг от друга. Определить расстояние между пунктами А и Г?

Задание 3

Найти длину кратчайшего пути между точками А и F.