Соедини каждый пункт с числом маршрутов, ведущих в него из А.
Реши задание на изображении
Сверь числа и знаки с фото.
[Рисунок: ориентированный граф, вершины в кружках с подписями. А — слева; правее и выше — Б; правее и ниже — В; правее — Г (сверху) и Д (снизу); далее — Е; крайняя справа — Ж. Стрелки: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Ж, Г→Е, Д→Е, Е→Ж.] Соедини каждый пункт с числом маршрутов, ведущих в него из А. Б ○ ○ 6 маршрутов Ж ○ ○ 2 маршрута Е ○ ○ 1 маршрут Г ○ ○ 4 маршрута
Краткий ответ
| Пункт | Число маршрутов из А | Что соединяем |
|---|---|---|
| Б | 1 | 1 маршрут |
| Г | 2 | 2 маршрута |
| Е | 4 | 4 маршрута |
| Ж | 6 | 6 маршрутов |
Почему так: принцип подсчёта
В графе число маршрутов в пункт равно сумме числа маршрутов во все пункты, из которых в него ведёт стрелка. Идём по графу слева направо, как по «волне».
1. Пункты, куда ведёт стрелка прямо из А. В них ровно по одному маршруту: \[ N(\text{Б})=1,\qquad N(\text{В})=1 \]
2. Пункт Г. В него ведут стрелки из Б и из В: \[ N(\text{Г})=N(\text{Б})+N(\text{В})=1+1=2 \]
3. Пункт Д. Тоже из Б и из В: \[ N(\text{Д})=1+1=2 \]
4. Пункт Е. В него ведут стрелки из Г и из Д: \[ N(\text{Е})=N(\text{Г})+N(\text{Д})=2+2=4 \]
5. Пункт Ж. В него ведут стрелки только из Г и из Е: \[ N(\text{Ж})=N(\text{Г})+N(\text{Е})=2+4=6 \]
Проверка
- Все маршруты в Ж обязательно проходят либо через Г, либо через Е — других стрелок в Ж нет, поэтому сумма \(2+4=6\) ничего не теряет и не считает дважды.
- Наборы чисел 1, 2, 4, 6 ровно совпадают с вариантами в задании (1 маршрут, 2 маршрута, 4 маршрута, 6 маршрутов), значит ни один вариант не остался лишним. ✔
Главное правило: не считай маршруты «в лоб» перебором, а складывай значения у предшественников — так работает для графа любой сложности.
