Учебник MAXIMUM Education

Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.

9 класс
Информатика

Поиск путей в графе

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

1. выделить начальную и конечную точки;

2. если есть дополнительно условие, то:

  1. отметить точки, через которые точно нужно пройти;

  2. отметить для них все входящие и исходящие ребра;

  3. удалить ненужные ребра;

  4. отметить все точки, через которые не нужно пройти;

  5. удалить для них все входящие и исходящие ребра;

3. использовать метод подсчета путей в графе:

  1. около первоначальной вершины написать 1;

  2. сосчитать количество путей около каждой вершины в зависимости от того, какие пути идут в ту или иную вершину;

  3. обойти таким образом каждую вершину графа;

4. записать ответ.

Пример задания с дополнительными условиями.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через город Ж, но не проходящих через город Г?

Пример решения задания.

Решение по этапам алгоритма, приведенного выше. Сначала выделим начальную и конечную точки на графе:

Отметим точки, через которые точно нужно пройти:

Отметим для них все входящие и исходящие ребра:

Удалим ненужные ребра:

Отметим все точки, через которые не нужно пройти:

Удалим для них все входящие и исходящие ребра:

Около первоначальной вершины напишем 1:

Сосчитаем количество путей около каждой вершины в зависимости от того, какие пути идут в ту или иную вершину. Обойдем таким образом каждую вершину графа:

Ответ: 4.