Задание 7 Параграф 14 ГДЗ Семакин 9 класс (Информатика)

1. Дан граф. Найдите количество путей, ведущих из вершины А в вершину К. Количество путей для каждой вершины из А записывайте в скобках рядом с названием вершины.

Обозначим в скобках количество путей из вершины А в каждую вершину графа.

Тогда:

$$Б=1,\quad В=2,\quad Г=1.$$

Далее считаем для следующих вершин:

$$Е=Б=1,$$

$$Д=Б=1,$$

$$Ж=В+Г=2+1=3,$$

$$З=Г=1.$$

Теперь найдём количество путей к вершине И:

$$И=Ж+З+Е=3+1+1=5.$$

И, наконец, к вершине К:

$$К=И+Е+Д=5+1+1=7.$$

Ответ

$$7$$