Урок 9-10. Решение задач на анализ и построение графов

Дата проведения занятия 2.10.19

Для описания графа часто используют квадратную таблицу, которая описывает все 

возможные связи между узлами.

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

Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и Е

(при условии, что передвигаться можно только по построенным дорогам).
Сначала преобразуем таблицу в вид, аналогичный графам, рассмотренным на
прошлом уроке, по этому графу и будем искать кратчайший путь.

Практическая работа:

Для решения следующих задач перейдите по ссылке Поляков-графы.

Домашняя работа:

Решите задачи