На рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей
Реши задание на изображении
Сверь числа и знаки с фото.
На рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город О?
[Рисунок: направленный граф; вершины А, Б, В, Г, Д, Е, Ё, Ж, З, И, К, Л, М, Н, О. Стрелки: А→Б, А→В, А→Г, Б→В, Б→Е, В→Д, В→Е, В→Ё, Г→Д, Д→Ё, Д→К, Е→Ё, Е→Ж, Ё→З, Ё→И, Ё→Л, Ж→З, Ж→Л, Ж→М, З→И, З→Л, И→К, И→Л, К→Н, Л→Н, Л→О, М→О, Н→О.]
Решить в тетради табличным и графическим (на графе) способами.
Ответ: 107 различных путей.
Считаем так: у вершины \(A\) ставим \(1\), а у каждой следующей — сумму чисел у вершин, из которых в неё идут стрелки. Идём в порядке \(А, Б, В, Г, Д, Е, Ё, Ж, З, И, К, Л, М, Н, О\).
| Вершина | Откуда приходят пути | Число путей |
|---|---|---|
| А | — | 1 |
| Б | А | 1 |
| В | А, Б | \(1+1=2\) |
| Г | А | 1 |
| Д | В, Г | \(2+1=3\) |
| Е | Б, В | \(1+2=3\) |
| Ё | В, Д, Е | \(2+3+3=8\) |
| Ж | Е | 3 |
| З | Ё, Ж | \(8+3=11\) |
| И | Ё, З | \(8+11=19\) |
| К | Д, И | \(3+19=22\) |
| Л | Ё, Ж, З, И | \(8+3+11+19=41\) |
| М | Ж | 3 |
| Н | К, Л | \(22+41=63\) |
| О | Л, М, Н | \(41+3+63=107\) |
Для графического способа на самой схеме подписываем у каждой вершины те же числа: \(A=1\), \(Б=1\), \(В=2\), …, \(Л=41\), \(Н=63\). В конце у вершины \(О\) получается:
\[ 41+3+63=107. \]
Проверка сходится: пути к \(О\) идут только из \(Л\), \(М\) и \(Н\).
