Ваш регион: Москва
ЕГЭ-пробный

Задача №15. Графы. Поиск количества путей.


Автор - Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

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

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

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

1
Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

2

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

3
Ответ: 11

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России)
                       +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Смотреть

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Позвоните мне

Все поля обязательны для заполнения

Отправить