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

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

Для описания графа можно использовать квадратную таблицу, которая задает все возможные связи между узлами. Но иногда удобнее представить граф в виде схемы. Представить один и тот же граф в виде таблицы и в виде схемы - этот прием часто используется при решении задач.
Решите задачу (№ 91) 
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Сначала преобразуем таблицу в вид, аналогичный графам, рассмотренным на прошлом уроке, по этому графу и будем искать кратчайший путь.
Длина кратчайшего пути такая: AD(12) + DC(2) + CE(4) + EZ(5) = 23 км

Работа на уроке в  тетрадях

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

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

1. Ответьте на вопросы формы до 22 час 16.10.23. 
2. Завершите работу, начатую в классе: Поляков-графы
3. Подготовьтесь к самостоятельной работе по графам, которая будет 17.10.23