1 тип. Определение количества путей
Решение: Пункт отправления (А) обозначаем за 1. Далее передвигаемся в последующие пункты. В пункт Г ведет только одна стрелка из А, значит количество дорог = 1. В Пункт В ведет две стрелки – из Г и из А, значит складываем количество дорог из Г(1) и из А(1) и получаем 2. В пункт Б ведет две стрелки – из В и из А, значит складываем количество дорог из В(2) и из А(1), получаем 3. Аналогично двигаемся для пункта К и получаем ответ 12.
2 тип. Подсчёт путей с избегаемой вершиной
Решение: Вначале, исключаем пути, проходящие через В и в дальнейшем их не учитываем. Далее, считаем количество путей как в предыдущей задачи. Получаем ответ 13.
3 тип. Подсчёт путей с избегаемой и обязательной вершиной
Решение: Сначала найдем уже известным нам способом количество путей, проходящих через город Г, но не проходящих через Л. Их будет 18
Затем найдем количество путей, проходящих через Л, но не проходящих через Г. Их будет 10. Таким образом количество путей, проходящих через пункт Г или через пункт Л, но не через оба этих пункта будет 18+10=28.
4 тип. Нахождение наибольшего (наименьшего) количества дорог, составляющих путь
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Решение: Начальную точку(А) принимаем за 0, так как в нее не ведет ни один путь. В Б и Д у нас ведет только один путь, значит он равен 1. В Г мы можем попасть через Д или из А, значит длина может быть равна 1 или 2, а так как мы ищем самый длинный путь, значит берем равный 2. В В у нас ведет три пути: из А, из Б и из Г, выбираем самый длинный, равный 3. Аналогично передвигаемся до конечной точки, выбирая наибольшую длину из возможных. Ответ: 7.
На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно передвигаться только в направлении, указанном стрелкой, для каждой дороги указано время проезда в минутах. За какое минимальное время можно проехать из пункта А в пункт Л? В ответе укажите только число — время в минутах, указывать единицы измерения не нужно.
Решение: Пункт отправления(А) обозначаем за 0. Время пути в пункт Б будет равно числу, указанному на единственной дороге, ведущей в этот пункт – 40. В пункт В – 60. В пункт Г ведут три дороги. Если пойдем из Б – время будет равно 40+30=70, из А – 90, из В – 60+20=80. Так как мы ищем минимальное, значит выбираем 70. Аналогично передвигаемся до последней точки и получаем ответ 200.
