ГИА В11
Графы
Пример 1 На рисунке схема дорог, связывающая города
А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном
направлении, указанном стрелкой. Сколько существует различных путей из города А
в город К?
Анализируем путь от города А до города Б и далее.
Возможные варианты: А-Б-Д-К, А-Б-К, А-Б-В-К.
Получили три варианта пути.
Путь из А в К через В только один – А-В-К.
Рассматриваем путь от А до Г и далее. Варианты:
А-Г-Е-К, А-Г-К, А-Г-В-К. Итого – три пути.
Всего вариантов: 3 + 1 + 3 =7.
Ответ: 7
|