А.З. На рисунке изображён граф. а) Найдите в этом графе кратчайший путь из вершины А в вершину В. Чему равна длина этого пути? Ответ: б) Сколько кратчайших путей ведёт из вершины С в вершину В? Ответ:

а) Чтобы найти кратчайший путь из вершины А в вершину В, посмотрим на граф. Можно пройти непосредственно по ребру AF, затем по ребру FB. Альтернативный путь A-C-D-E-B длиннее. Таким образом, кратчайший путь – A-F-B. Длина этого пути равна количеству ребер, то есть 2.

Ответ: A-F-B, длина 2

б) Чтобы найти количество кратчайших путей из вершины С в вершину В, посмотрим на граф. Кратчайшие пути C-D-E-B и C-A-F-B.

Ответ: 2