Контрольные задания
Вопрос:

Задание 3. Постройте граф (схему дорог) между городами А, В, С, D, Е. Дороги: А-В, A-C, B-D, C-D, D-E. Сколько существует различных путей из А в Е, не проходящих дважды через одну вершину? Перечислите все пути или укажите их количество.

Фото заданияОткрыть фото

Ответ:

Решение:

Построим граф, где вершины — города, а рёбра — дороги.

ABCDEA-BA-CB-DC-DD-E

Теперь найдём все пути из А в Е, не проходящие дважды через одну вершину:

  1. A → B → D → E
  2. A → C → D → E

Ответ: Существует 2 пути: A → B → D → E и A → C → D → E.

📄 Все решения с фото📸 Фото ГДЗ

Похожие