Ориентированный граф

В9. Задача на «количество различных путей из одной вершины в другую»
Ориентированный граф.
Разрешимость задачи требует отсутствия циклов.

Задача на «количество различных путей из одной вершины в другую»
Способ 1. Перебор всех возможных путей «методом наблюдения»
Все пути с АБ:
АБДИЛ, АБДЖЛ, АБВДИЛ, АБВДЖЛ, АБВЖЛ
2. Все пути с АВ:
АВДИЛ, АВДЖЛ, АВЖЛ
3. Все пути с АГ:
АГВДИЛ, АГВДЖЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ
13 ПУТЕЙ

Все пути с АБ:
АБДЛ, АБДИЛ, АБВДИЛ, АБВДЛ, АБВЖЛ
2. Все пути с АВ:
АВЖЛ, АВДИЛ, АВДЛ
3. Все пути с АГ:
АГВДИЛ, АГВДЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ
13 ПУТЕЙ

2013-В9. Задача на «количество различных путей из одной вершины в другую»
Способ 2. Пошаговое построение всех возможных путей
Все вершины из А:
АБ, АВ, АГ
2. Все вершины, содержащие
2 ребра:
АБД, АБВ, АВД, АВЖ, АГВ, АГЕ
3. Все вершины, содержащие 3 ребра:
АБДИ, АБДЖ, АБВД, АБВЖ, АВДИ, АВДЖ, АВЖЛ, АГВД, АГВЖ, АГЕЖ, АГЕК
4. Все вершины, содержащие 4 ребра: АБДИЛ, АБДЖЛ, АБВДИ, АБВДЖ, АБВЖЛ, АВДИЛ, АВДЖЛ, АГВДИ, АГВДЖ, АГВЖЛ, АГЕЖЛ, АГЕКЛ
5. Все вершины, содержащие 5 ребер: АБВДИЛ, АБВДЖЛ, АГВДИЛ, АГВДЖЛ
13 ПУТЕЙ

Задача на «количество различных путей из одной вершины в другую»
Способ 3. Подстановка 1.
13 ПУТЕЙ
1. Вершины, в которые можно прибыть
только из А: NБ=NГ=1
2. NЛ=NИ+NЖ+NК=
=NД+(NД+NВ+NЕ)+NЕ=
=2NД+2NЕ+NВ= 2(NБ+NВ)+2NГ+NВ=
=2NБ+2NГ+3(NБ+NА+NГ)=2+2+9=13

Задача на «количество различных путей из одной вершины в другую»
Способ 4. Подстановка 2.
13 ПУТЕЙ

Задача на «количество различных путей из одной вершины в другую»
Задачи для тренировки