Задача к ЕГЭ по информатике на тему «графы» №1

На рисунке  — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, К.

PIC

Сколько существует различных путей, не проходящих через город В, из пункта А в пункт К?

Не проходящих через пункт В, значит, что можно стереть все пути входящие и исходящие из вершины В. Тогда в Б и Г существует всего одна дорога. Обе дороги из Б и Г ведут в пункт Д. Из Д в Е и Ж идёт так же по две дороги. Получается что в К идут по две дороги из Д, Е и Ж. 2 ∗3 = 6  .

Ответ: 6
Оцените статью
Я решу все!