2015-05-12
1069
Теперь выпишем пути, которые начинаются с ребра АВ (также сверху вниз):
АВДИК, АВДК, АВЖК
и, наконец, пути, начинающиеся с участка АГ:
АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК.
Всего получилось 13 путей. Это наиболее простой метод, но он нередко приводит к неправильному результату, потому что легко пропустить какойто путь.
Способ 2. Пошаговое построение всех возможных путей.
Сначала рассмотрим все вершины, куда можно попасть из начальной вершины А за один шаг:
АБ
АВ
АГ
Теперь выписываем все пути из вершины A, содержащие два ребра (продолжения уже построенных путей на одно ребро):
АБД АБВ
АВД АВЖ
АГВ АГЕ
Следующий шаг (в рамку обведены пути, дошедшие до конечного пункта K):
АБДИ АБДК АБВД АБВЖ
АВДИ АВДК АВЖК
АГВД АГВЖ АГЕЖ АГЕК
Итак, четыре пути из А в К мы уже нашли. Продолжая движение по остальным маршрутам, находим семь путей, состоящих из четырех ребер:
АБДИК АБВДИ АБВДК АБВЖК
АВДИК
АГВДИ АВГДК АГВЖК АГЕЖК
и далее два пути из пяти ребер:
АБВДИК
АГВДИК
Таким образом, всего найдено 4 + 7 + 2 = 13 путей, причем по построению других путей нет (в списке не осталось путей, не доведенных до конечной точки).
|
|
|
Этот способ более надежен, чем предыдущий, поскольку на каждом шаге нас интересуют только ребра, исходящие из одной вершины. Это значит, что нужно анализировать не весь граф, а только его небольшую часть, поэтому труднее ошибиться.
Задачи для тренировки
На рисунке показана схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
