Количество разных путей между вершинами графа

Задача № 9 ОГЭ по информатике

В этой задаче нам дан направленный ненагруженный граф. Направленный граф ещё называется ориентированным или орграфом. А ненагруженный или невзвешенный — значит, что его связям не назначены числа — веса.

От нас требуется подсчитать количество всевозможных путей между заданными вершинами этого графа. Иногда дают ещё дополнительные условия: нам либо нельзя проходить по пути через заданную вершину, либо мы обязаны пройти через неё.

Граф может выглядеть, например, так:

Для решения будем использовать приём, который называется динамическим программированием. На самом деле, он не имеет прямого отношения к программированию — это математический метод.

Суть динамического программирования в том, что для вычисления значений на каждом следующем этапе мы используем значения, сохранённые на предыдущем.

Например, для вычисления факториала числа n этим методом мы могли бы заполнить таблицу:

Напомню, что факториал n! = 1 * 2 * 3 *… * n. Видно, что для получения каждого следующего результата мы умножаем текущее n (сиреневое) на результат n! предыдущего шага (это показано синими стрелками).

Давайте посмотрим, как мы можем использовать динамическое программирование для поиска количества путей в графе. Найдём количество разных путей между вершинами А и F.

1) В начальную вершину А мы можем попасть единственным путём: просто оказаться там. Значит в А ведёт один возможный путь. Отметим его возле начальной вершины.

2) Теперь на каждой связи, выходящей из А, запишем число, равное сумме чисел, входящих в А (то есть везде единицы).

3) То же самое повторим для всех следующих вершин: на связях, выходящих из вершины, будем писать число, равное сумме чисел на связях, входящих в эту вершину.

Например, в D входит одна единица, значит у связи D-E ставим тоже единицу. А вот в Е теперь входят две связи с единицами, значит на связях Е-G и E-H поставим двойки.

И так до конца. Главное: для каждой вершины нам уже должны быть известны числа входящих в неё связей.

4) А теперь самое вкусное. Посчитаем сумму чисел всех связей, входящих в последнюю вершину F и — вуаля! Мы получили готовый ответ:

ДОПОЛНИТЕЛЬНЫЕ УСЛОВИЯ

Пусть теперь в этой задаче нам нельзя проходить через вершину D. Тогда в начало добавим ещё один этап: нужно вычеркнуть все участки маршрута, проходящие через D.

В нашем случае пропадут связи А-D, D-E и D-G. Все остальные останутся «рабочими».

Осталось расставить числа, как мы это делали раньше:

Видите? Теперь из Е выходит сумма 1, потому что связь D-E нерабочая. А в G суммируются три связи, а не четыре. И результат получился 5.

Для задач с дополнительными условиями результат всегда получится меньше, чем для простой задачи на том же графе.

Теперь пусть мы, наоборот, обязаны пройти через вершину D. Значит, нам нужно вычеркнуть все связи, пройдя через которые мы в D не попадаем.

Например, A-C и следующая C-G: из вершины С нам уже никак не вернуться в D. То же для A-B и затем B-F.

A-E вычёркиваем, но сама вершина Е будет работать, ведь мы можем попасть в неё из D и пойти дальше — в Н и G.

Расставим числа-суммы как раньше.

Получилось ещё меньше — 4. Логично: чем меньше связей участвует в расчёте, тем меньшим количеством разных путей мы можем добраться из начальной вершины до конечной.

Теперь вы точно знаете, как решать задачу № 9 из ОГЭ по информатике. Осталось потренироваться!