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

  Дата проведения занятия  8а1 14.10.25
Дата проведения занятия  8а2 13.10.25
Дата проведения занятия  8б   13.10.25

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

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

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

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

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

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

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

  8б   14.10.25

  8а2 15.10.25

  8а1 16.10.25