Сверь числа и знаки с фото.
- Тип 9 № 11025 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж, но не проходящих через город К? [Рисунок: ориентированный граф с вершинами А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М; направления дорог показаны стрелками.]
- Тип 9 № 43728 На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город F? [Рисунок: ориентированный граф с вершинами A, B, C, D, E, F, G, H и стрелками.]
- Тип 9 № 11019 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город П, проходящих через город Е? [Рисунок: ориентированный граф с вершинами А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П и стрелками.]
- Тип 9 № 42029 На рисунке — схема дорог, связывающих города A, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город К? [Рисунок: ориентированный граф с вершинами A, Б, В, Г, Д, Е, Ж, З, И, К и стрелками.]
- Тип 4 № 4556 Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых приведена в таблице. [Таблица: A-B=3, A-C=5, A-D=6, A-E=3; B-C=1, B-D=4, B-E=3; C-D=1, C-E=6; D-E=3.] Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).
- Тип 4 № 23 [Таблица: A-B=5, A-D=3; B-C=1, B-E=4; C-D=6.] Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).
- Тип 4 № 4342 [Таблица: A-B=2; B-C=1; C-D=1, C-E=2; D-E=1.] Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
На фото несколько отдельных номеров; я решил все. Кратко:
| Задание | Ответ |
|---|---|
| 26 | 9 |
| 27 | 5 |
| 28 | 9 |
| 29 | 12 |
| 16 | 5 |
| 17 | 3 |
| 18 | 5 |
Задания 26–29: подсчёт путей
Главный принцип: в направленном графе число путей до вершины равно сумме путей, приходящих в неё по входящим стрелкам. Если путь обязан проходить через фиксированную вершину, удобно считать отдельно: сколько путей дойти до неё и сколько путей пройти от неё до финиша, а затем перемножить.
26. До города Ж ведут 3 варианта пути. От Ж до М без захода в К есть 3 варианта: через Л, через И и через И—Л.
Значит, \(3\cdot3=9\).27. Выписываем все пути A → F:
- A—B—F
- A—C—G—F
- A—D—G—F
- A—E—G—F
- A—E—H—F
Итого 5.
28. До Е можно дойти 3 способами. После Е путь идёт через Ж, а от Ж до П есть 3 варианта: напрямую, через К и через Н.
Получаем \(3\cdot3=9\).29. До Ж — 4 пути. От Ж до К — 3 варианта: напрямую, через И и через З.
Тогда \(4\cdot3=12\).
Задания 16–18: кратчайший путь
16. Путь A—B—C—D:
\(3+1+1=5\).
Прямая дорога A—D равна 6, поэтому она не минимальна. Ответ: 5.17. В таблице есть прямая дорога A—D длины 3, и более короткого пути по таблице нет. Ответ: 3.
18. Путь A—B—C—D—E:
\(2+1+1+1=5\).
Через C—E тоже получается \(2+1+2=5\). Ответ: 5.