реши три задачи
Сверь числа и знаки с фото.
[Рисунок: схема из семи кружков с подписями А, Б, В, Г, Д, Е, Ж, соединённых зелёными стрелками: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Ж, Г→Е, Д→Е, Е→Ж] Заполни два поля. Каждый ответ — одно целое число. Маршрутов выписано перебором: Вес вершины Е: Вес вершины Ж:
[Рисунок: схема из семи кружков с подписями А, Б, В, Г, Д, Е, Ж, соединённых зелёными стрелками: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Ж, Г→Е, Д→Е, Е→Ж] Заполни три поля. Каждый ответ — одно целое число. Маршрутов из А в Г: Маршрутов из Д в Ж: Всего маршрутов из А в Ж через Д:
На схеме показаны дороги с односторонним движением между пунктами А, Б, В, Г, Д, Е и Ж. Проехать можно только по стрелке. [Рисунок: схема из семи кружков с подписями А, Б, В, Г, Д, Е, Ж, соединённых зелёными стрелками: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Ж, Г→Е, Д→Е, Е→Ж] Сколько маршрутов из А в Ж не проходят через пункт Е? Введи одно целое число. Ответ: ___
Кратко: ответы
Фото 1. Маршрутов выписано перебором: 6. Вес вершины Е: 4. Вес вершины Ж: 6.
Фото 2. Маршрутов из А в Г: 2. Маршрутов из Д в Ж: 1. Всего маршрутов из А в Ж через Д: 2.
Фото 3. Маршрутов из А в Ж, не проходящих через Е: 2.
Как устроена схема
Рёбра (все стрелки односторонние):
- А → Б, А → В
- Б → Г, Б → Д
- В → Г, В → Д
- Г → Ж, Г → Е
- Д → Е
- Е → Ж
Обрати внимание: линии Б→Д и В→Г пересекаются, но это разные дороги — одна идёт сверху вниз, другая снизу вверх.
Главная идея: вес вершины
Вес вершины — это число маршрутов из начальной вершины А до неё. Считаем по порядку слева направо:
\[w(\text{А})=1\]
\[w(\text{Б})=w(\text{А})=1,\quad w(\text{В})=w(\text{А})=1\]
\[w(\text{Г})=w(\text{Б})+w(\text{В})=1+1=2\]
\[w(\text{Д})=w(\text{Б})+w(\text{В})=1+1=2\]
\[w(\text{Е})=w(\text{Г})+w(\text{Д})=2+2=4\]
\[w(\text{Ж})=w(\text{Г})+w(\text{Е})=2+4=6\]
Правило простое: вес вершины равен сумме весов всех вершин, из которых в неё ведёт стрелка.
Проверка перебором (фото 1)
Все маршруты из А в Ж:
- А→Б→Г→Ж
- А→Б→Г→Е→Ж
- А→Б→Д→Е→Ж
- А→В→Г→Ж
- А→В→Г→Е→Ж
- А→В→Д→Е→Ж
Их ровно 6 — совпало с \(w(\text{Ж})=6\), а через Е проходит 4 из них, то есть \(w(\text{Е})=4\).
Фото 2
- Из А в Г: А→Б→Г и А→В→Г, то есть \(w(\text{Г})=2\).
- Из Д в Ж: у Д единственная дорога — в Е, а из Е единственная — в Ж. Значит, только Д→Е→Ж, ответ 1.
- Из А в Ж через Д: до Д ведут 2 маршрута, от Д до Ж — 1, перемножаем: \(2\cdot 1=2\). Это А→Б→Д→Е→Ж и А→В→Д→Е→Ж.
Фото 3
Всего маршрутов 6, через Е проходит 4 (\(w(\text{Е})=4\)), значит без Е:
\[6-4=2\]
Это А→Б→Г→Ж и А→В→Г→Ж — единственные пути, где после Г сразу идём в Ж.
