Задание №13 — Количество путей в ориентированном графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза. 
Правильный ответ
21
Пояснение
Решение:
Выпишем по рисунку все дороги (стрелки):
А → Б, А → Г, Б → Д, В → А, В → Б, В → Г, В → Д, Г → Е, Г → Ж, Д → Е, Д → И, Д → Л, Е → В, Е → Л, Ж → Е, И → Л, К → Ж, Л → Ж, Л → К.
Нужны замкнутые маршруты Е → … → Е, в которых Е не встречается внутри, а каждый промежуточный город — не более одного раза. Из Е выходят только две дороги: в В и в Л, поэтому разберём два случая.
1) Первый шаг Е → Л. Из Л: Л → Ж → Е и Л → К → Ж → Е — 2 маршрута.
2) Первый шаг Е → В. Посчитаем сначала два вспомогательных числа.
- Из Г в Е: Г → Е и Г → Ж → Е — 2 способа.
- Из Д в Е: Д → Е (1 способ); Д → Л →… и Д → И → Л →…, а из Л в Е ведут 2 маршрута (через Ж и через К, Ж). Итого способов.
Из В выходят четыре дороги:
- В → Г →… → Е — 2;
- В → Д →… → Е — 5;
- В → Б → Д →… → Е — 5;
- В → А, а из А либо А → Г (2), либо А → Б → Д (5) — всего 7.
Значит, во втором случае маршрутов.
Всего .
g = {
'А': ['Б', 'Г'],
'Б': ['Д'],
'В': ['А', 'Б', 'Г', 'Д'],
'Г': ['Е', 'Ж'],
'Д': ['Е', 'И', 'Л'],
'Е': ['В', 'Л'],
'Ж': ['Е'],
'И': ['Л'],
'К': ['Ж'],
'Л': ['Ж', 'К'],
}
total = 0
def go(v, used):
global total
for u in g[v]:
if u == 'Е': # вернулись в Е - маршрут готов
total += 1
elif u not in used: # промежуточный город - не более одного раза
go(u, used | {u})
go('Е', set())
print(total) # 21Ответ: 21