Задание 2. Тип заданий 15: поиск путей в графе.
  • Задание:

    На рисунке показана схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I?

    граф, схема дорог

  • Решение:

    Для решения развернём нашу схему дорог

    Шаг 1. Из пункта А пути ведут в пункты B, C, D, E и F:

    Шаг 2. Из пункта B только один путь — в пункт G, из которого тоже один путь в пункт I:

    Пункт I — конечный, обведём его кружном, чтобы в конце было легче считать пути.

    Шаг 3. Из пункта C только один путь — в пункт B, из которого только один путь в пункт I. Всю дорогу рисовать не будем, отметим только, что из пункта C один путь в пункт I:

    Шаг 4. Аналогично разберёмся с пунктами E и F. Пункт D трогать пока не имеет смысла, к нему вернёмся, когда узнаем количество путей из E и F:

    Шаг 5. Из пункта D пути ведут в C. G, H и E, из которых ведут по одному пути в пункт I, и один путь сразу в пункт I:

    Остаётся подсчитать. Всего получилось девять кружков, каждый кружок обозначает только один путь в I.

    Ответ: 9

Поделиться:
 
Комментарии (0)

Нет комментариев. Ваш будет первым!

Перевести число из в Результат: 510 = 1012