Рабочая тетрадь к уроку «Графы. Поиск количества путей 1) На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М? 2) На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г? На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, М, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город л, не проходящих через город В?

Ответ: 1) 6; 2) 2; 3) 4

Решение:

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

• A → Б → В → К → M (1 путь)
• A → Б → Ж → К → M (2 путь)
• A → Д → Ж → К → M (3 путь)
• A → Д → И → Л → M (4 путь)
• A → Д → И → K → M (5 путь)
• A → Г → И → Л → M (6 путь)

Всего 6 различных путей.

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

• A → Г → И → Л → M (1 путь)
• A → Г → И → К → M (2 путь)

Всего 2 пути, проходящих через город Г.

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

• A → Г → И → Л (1 путь)
• A → Д → Е → Л (2 путь)
• A → Д → Ж → З → Л (3 путь)
• A → Д → И → Л (4 путь)

Всего 4 пути, не проходящих через город В.

Ответ: 1) 6; 2) 2; 3) 4

Grammar Ninja

Минус 15 минут нудной домашки. Потрать их на катку или новый рилс

Выручи свою тиму — отправь ссылку другу. Карма +100 обеспечена