1. Изучить использование графов при решении задач, будет проверочная работа.

Краткий конспект

• Граф состоит из вершин и соединяющих их рёбер. В задачах о дорогах вершины обозначают населённые пункты, а рёбра — дороги.
• Если у дороги указана длина, граф взвешенный: вес ребра равен длине дороги. Если направление движения ограничено стрелкой, граф ориентированный.
• Путь — последовательность рёбер, ведущая из одной вершины в другую. Длину пути с указанными весами находят сложением весов его рёбер.
• Чтобы найти кратчайший путь, сравнивают длины возможных путей. Чтобы посчитать число путей в ориентированном графе, перечисляют допустимые последовательности рёбер, соблюдая направление стрелок.