Домашнее задание для 9 тех класса по информатике на пятницу 05.12.25:
1. Прочитайте §2.3 учебника. Повторите материал тем "Графы. Взвешенные графы. Ориентированные графы" онлайн презентаций (с примерами решения задач) по ссылкам
2. Решите (письменно) задачи по теме "Поиск оптимальных путей в графе. Количество путей в графе" (в решении в задачах 1 и 2 нужно построить сам граф и найти нужный маршрут методом Дийкстры или деревом возможных путей в графе, а для третьей задачи решить её через подсчёт степеней вершин):
2.1 Между населёнными пунктами A, B, C, D, E построены дороги, стоимость перевозки по которым приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите МАКСИМАЛЬНУЮ стоимость перевозки груза из A в E при условии, что маршрут не может проходить через какой-то пункт более одного раза. Постройте граф по весовой матрице и определите маршрут максимальной стоимости. В ответе запишите стоимость и сам путь.
2.2 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в B. Постройте граф по весовой матрице и определите маршрут максимальной стоимости. В ответе запишите длину и сам путь.
2.3 Вычислите количество различных путей из вершины А в вершину К для ориентированного графа (решение приведите через подсчёт сумм степеней вершин графа):
Решение задач нужно сдать на проверку перед уроком 05.12.25 или прислать фотографии решений по электронной почте:
