Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.
Поиск путей в графе
Одно из заданий экзамена посвящено поиску количества путей в ориентированном графе. Для того, чтобы без труда решать любой прототип данного задания, достаточно знать всего лишь один алгоритм:
1. выделить начальную и конечную точки;
2. если есть дополнительно условие, то:
-
отметить точки, через которые точно нужно пройти;
-
отметить для них все входящие и исходящие ребра;
-
удалить ненужные ребра;
-
отметить все точки, через которые не нужно пройти;
-
удалить для них все входящие и исходящие ребра;
3. использовать метод подсчета путей в графе:
-
около первоначальной вершины написать 1;
-
сосчитать количество путей около каждой вершины в зависимости от того, какие пути идут в ту или иную вершину;
-
обойти таким образом каждую вершину графа;
4. записать ответ.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через город Ж, но не проходящих через город Г?
Пример решения задания.
Решение по этапам алгоритма, приведенного выше. Сначала выделим начальную и конечную точки на графе:
Отметим точки, через которые точно нужно пройти:
Отметим для них все входящие и исходящие ребра:
Удалим ненужные ребра:
Отметим все точки, через которые не нужно пройти:
Удалим для них все входящие и исходящие ребра:
Около первоначальной вершины напишем 1:
Сосчитаем количество путей около каждой вершины в зависимости от того, какие пути идут в ту или иную вершину. Обойдем таким образом каждую вершину графа:
Ответ: 4.