ГИА В11 Графы

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

Анализируем путь от города А до города Б и далее.

Возможные варианты: А-Б-Д-К, А-Б-К, А-Б-В-К. Получили три варианта пути.

Путь из А в К через В только один – А-В-К.

Рассматриваем путь от А до Г и далее. Варианты: А-Г-Е-К, А-Г-К, А-Г-В-К. Итого – три пути.  Всего вариантов: 3 + 1 + 3 =7.

Ответ: 7