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

Ответ: 8

1. Схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З:

• A → Б → E → З (1 путь)
• A → Б → Г → E → З (1 путь)
• A → Б → Г → Д → З (1 путь)
• A → В → Г → E → З (1 путь)
• A → В → Г → Д → З (1 путь)
• A → В → Д → З (1 путь)
• A → В → Ж → З (1 путь)
• A → В → * → З (1 путь)

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

Ответ: 8

Ответ: 12

2. Схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К:

• A → Б → Ж → К (1 путь)
• A → Б → * → К (1 путь)
• A → Б → E → К (1 путь)
• A → В → Ж → К (1 путь)
• A → В → * → К (1 путь)
• A → В → E → К (1 путь)
• A → Г → Ж → К (1 путь)
• A → Г → * → К (1 путь)
• A → Г → E → К (1 путь)
• A → Г → Д → * → К (1 путь)
• A → Г → Д → И → К (1 путь)
• A → Г → Д → К (1 путь)

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

Ответ: 12

Ответ: 10

3. Схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И:

• A → Б → * → И (1 путь)
• A → Б → E → И (1 путь)
• A → В → * → И (1 путь)
• A → В → E → И (1 путь)
• A → Г → * → И (1 путь)
• A → Г → E → И (1 путь)
• A → Г → Д → И (1 путь)
• A → Г → В → * → И (1 путь)
• A → Г → В → E → И (1 путь)
• A → Г → В → Б → * → И (1 путь)

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

Ответ: 10