Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами.
Решите задачу (№ 91)
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Решите задачу (№ 91)
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Сначала преобразуем таблицу в вид, аналогичный графам, рассмотренным на прошлом уроке, по этому графу и будем искать кратчайший путь.
Длина кратчайшего пути такая: AD(12) + DC(2) + CE(4) + EZ(5) = 23 км
Сначала преобразуем таблицу в вид, аналогичный графам, рассмотренным на прошлом уроке, по этому графу и будем искать кратчайший путь.
Длина кратчайшего пути такая: AD(12) + DC(2) + CE(4) + EZ(5) = 23 км
Домашнее задание на 25.01.18
- Посмотрите на графы ЗДЕСЬ
- Нарисуйте эти графы в тетради.
- Вычислите и запишите в тетради, сколько существует различных путей для разных графов:
- а) из начальной точки А в конечную точку Д,
- б) из начальной точки А в конечную точку Е,
- в) из начальной точки А в конечную точку К, не проходящих через Ж
Комментариев нет:
Отправить комментарий