На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К?
Посчитаем число путей в каждом городе слева направо. В Е ведут 3 пути, в Ж — 7 путей, в З — 10 путей.
В К ведут пути из Е, Ж и З: 3 + 7 + 10 = 20.
Ответ: 20.
Посчитаем число путей в каждом городе слева направо. В Е ведут 3 пути, в Ж — 7 путей, в З — 10 путей.
В К ведут пути из Е, Ж и З: 3 + 7 + 10 = 20.
Ответ: 20.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, не проходящих через город З?
Всего путей из А в К: 20.
Через З проходят 8 путей.
Искомое количество: 20 − 8 = 12.
Ответ: 12.
Всего путей из А в К: 20.
Через З проходят 8 путей.
Искомое количество: 20 − 8 = 12.
Ответ: 12.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, не проходящих через город Г?
Всего из А в К существует 13 путей.
Через город Г проходят 3 пути.
Следовательно, путей, не проходящих через Г: 13 − 3 = 10.
Ответ: 10.
Всего из А в К существует 13 путей.
Через город Г проходят 3 пути.
Следовательно, путей, не проходящих через Г: 13 − 3 = 10.
Ответ: 10.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Ж?
Количество путей из А в Ж равно 7.
Из Ж в К можно попасть 2 способами: напрямую или через З.
По правилу умножения получаем: 7 · 2 = 14.
Ответ: 14.
Количество путей из А в Ж равно 7.
Из Ж в К можно попасть 2 способами: напрямую или через З.
По правилу умножения получаем: 7 · 2 = 14.
Ответ: 14.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Е?
В город Е можно попасть двумя способами: А–Б–Е и А–В–Е.
Из Е в К есть три пути: Е–К, Е–З–К и Е–И–К.
Следовательно, путей через Е: 2 · 3 = 6.
Ответ: 6.
В город Е можно попасть двумя способами: А–Б–Е и А–В–Е.
Из Е в К есть три пути: Е–К, Е–З–К и Е–И–К.
Следовательно, путей через Е: 2 · 3 = 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город З?
В город З ведут пять путей из А: А–В–З, А–Г–З, А–Б–Е–З, А–Б–Ж–З, А–В–Ж–З.
Из З в К ведёт одна дорога. Поэтому количество путей из А в К через З равно 5 · 1 = 5.
Ответ: 5.
В город З ведут пять путей из А: А–В–З, А–Г–З, А–Б–Е–З, А–Б–Ж–З, А–В–Ж–З.
Из З в К ведёт одна дорога. Поэтому количество путей из А в К через З равно 5 · 1 = 5.
Ответ: 5.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Ж?
Сначала посчитаем пути из А в Ж: А–Б–Ж, А–Г–Ж, А–Б–Е–Ж, А–В–Е–Ж. Таких путей 4.
Из Ж в К можно попасть двумя способами: напрямую или через З. Следовательно, путей из Ж в К — 2.
Всего путей через Ж: 4 · 2 = 8.
Ответ: 8.
Сначала посчитаем пути из А в Ж: А–Б–Ж, А–Г–Ж, А–Б–Е–Ж, А–В–Е–Ж. Таких путей 4.
Из Ж в К можно попасть двумя способами: напрямую или через З. Следовательно, путей из Ж в К — 2.
Всего путей через Ж: 4 · 2 = 8.
Ответ: 8.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Д?
В город Д из А можно попасть двумя путями: А–Б–Д и А–В–Д.
Из Д в К есть три пути: Д–Ж–К, Д–З–К и Д–И–К.
Общее число путей через Д равно 2 · 3 = 6.
Ответ: 6.
В город Д из А можно попасть двумя путями: А–Б–Д и А–В–Д.
Из Д в К есть три пути: Д–Ж–К, Д–З–К и Д–И–К.
Общее число путей через Д равно 2 · 3 = 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Е?
В город Е ведут два пути из А: А–Б–Е и А–В–Е.
Из Е в К можно попасть двумя способами: Е–И–К и Е–З–К.
Число путей через Е: 2 · 2 = 4.
Ответ: 4.
В город Е ведут два пути из А: А–Б–Е и А–В–Е.
Из Е в К можно попасть двумя способами: Е–И–К и Е–З–К.
Число путей через Е: 2 · 2 = 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Е?
Посчитаем количество путей из А в Е: А–Б–Е и А–В–Е. Таких путей 2.
Из Е в К есть два пути: Е–З–К и Е–И–К.
По правилу умножения общее число путей через Е равно 2 · 2 = 4.
Ответ: 4.
Посчитаем количество путей из А в Е: А–Б–Е и А–В–Е. Таких путей 2.
Из Е в К есть два пути: Е–З–К и Е–И–К.
По правилу умножения общее число путей через Е равно 2 · 2 = 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| А | Ж |
| Б | В |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | И |
| Д | И |
| Е | Ж |
| Е | К |
| Ж | З |
| Ж | К |
| З | К |
| И | К |
Сколько существует различных путей из города А в город К, проходящих через город Ж?
До города Ж можно добраться 6 способами: напрямую, через Б, через В, через Б–В, через Б–Е и через Г.
Из Ж в К есть 2 пути: напрямую и через З. Итого: 6 · 2 = 12.
Ответ: 12.
До города Ж можно добраться 6 способами: напрямую, через Б, через В, через Б–В, через Б–Е и через Г.
Из Ж в К есть 2 пути: напрямую и через З. Итого: 6 · 2 = 12.
Ответ: 12.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | З |
| Г | И |
| Д | И |
| Е | Ж |
| Е | К |
| З | Ж |
| Ж | К |
| И | К |
Сколько существует различных путей из города А в город К, проходящих через город Ж?
До города Ж можно добраться 5 способами: через Б, через В, через Г, через Б–Е и через Г–З.
Из Ж в К есть 1 путь. Итого: 5 · 1 = 5.
Ответ: 5.
До города Ж можно добраться 5 способами: через Б, через В, через Г, через Б–Е и через Г–З.
Из Ж в К есть 1 путь. Итого: 5 · 1 = 5.
Ответ: 5.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | З |
| Г | И |
| Д | И |
| Е | Ж |
| Е | К |
| Ж | З |
| Ж | К |
| И | З |
| И | К |
| З | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей до К с конца: N(К)=1, N(З)=1, N(И)=2, N(Ж)=2, N(Е)=3, N(Д)=2, N(Г)=5, N(В)=2, N(Б)=5.
N(А)=5+2+5+2=14.
Ответ: 14.
Считаем количество путей до К с конца: N(К)=1, N(З)=1, N(И)=2, N(Ж)=2, N(Е)=3, N(Д)=2, N(Г)=5, N(В)=2, N(Б)=5.
N(А)=5+2+5+2=14.
Ответ: 14.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| А | Ж |
| Б | В |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | И |
| Д | И |
| Е | Ж |
| Е | К |
| Ж | З |
| Ж | К |
| З | К |
| И | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей с конца.
- N(К)=1.
- N(З)=1.
- N(И)=1.
- N(Ж)=N(З)+N(К)=1+1=2.
- N(Е)=N(Ж)+N(К)=2+1=3.
- N(Д)=N(И)=1.
- N(Г)=N(Ж)+N(И)=2+1=3.
- N(В)=N(Ж)=2.
- N(Б)=N(В)+N(Е)+N(Ж)=2+3+2=7.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)+N(Ж)=7+2+3+1+2=15.
Ответ: 15.
Считаем количество путей с конца.
- N(К)=1.
- N(З)=1.
- N(И)=1.
- N(Ж)=N(З)+N(К)=1+1=2.
- N(Е)=N(Ж)+N(К)=2+1=3.
- N(Д)=N(И)=1.
- N(Г)=N(Ж)+N(И)=2+1=3.
- N(В)=N(Ж)=2.
- N(Б)=N(В)+N(Е)+N(Ж)=2+3+2=7.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)+N(Ж)=7+2+3+1+2=15.
Ответ: 15.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | З |
| Г | И |
| Д | И |
| Е | Ж |
| Е | К |
| З | Ж |
| Ж | К |
| И | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей с конца.
- N(К)=1.
- N(Ж)=1.
- N(И)=1.
- N(З)=N(Ж)=1.
- N(Е)=N(Ж)+N(К)=1+1=2.
- N(Д)=N(И)=1.
- N(Г)=N(Ж)+N(З)+N(И)=1+1+1=3.
- N(В)=N(Ж)=1.
- N(Б)=N(Е)+N(Ж)=2+1=3.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=3+1+3+1=8.
Ответ: 8.
Считаем количество путей с конца.
- N(К)=1.
- N(Ж)=1.
- N(И)=1.
- N(З)=N(Ж)=1.
- N(Е)=N(Ж)+N(К)=1+1=2.
- N(Д)=N(И)=1.
- N(Г)=N(Ж)+N(З)+N(И)=1+1+1=3.
- N(В)=N(Ж)=1.
- N(Б)=N(Е)+N(Ж)=2+1=3.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=3+1+3+1=8.
Ответ: 8.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| А | Е |
| Б | Д |
| В | Ж |
| В | З |
| Г | З |
| Д | Е |
| Д | К |
| Ж | Е |
| Ж | К |
| З | Ж |
| З | К |
| Е | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей с конца.
- N(К)=1.
- N(Е)=1.
- N(Ж)=N(Е)+N(К)=1+1=2.
- N(З)=N(Ж)+N(К)=2+1=3.
- N(Д)=N(Е)+N(К)=1+1=2.
- N(Г)=N(З)=3.
- N(В)=N(Ж)+N(З)=2+3=5.
- N(Б)=N(Д)=2.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)+N(Е)=2+5+3+2+1=13.
Ответ: 13.
Считаем количество путей с конца.
- N(К)=1.
- N(Е)=1.
- N(Ж)=N(Е)+N(К)=1+1=2.
- N(З)=N(Ж)+N(К)=2+1=3.
- N(Д)=N(Е)+N(К)=1+1=2.
- N(Г)=N(З)=3.
- N(В)=N(Ж)+N(З)=2+3=5.
- N(Б)=N(Д)=2.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)+N(Е)=2+5+3+2+1=13.
Ответ: 13.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | З |
| Д | З |
| Е | Ж |
| З | Ж |
| Ж | И |
| Ж | К |
| И | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей с конца.
- N(К)=1.
- N(И)=N(К)=1.
- N(Ж)=N(К)+N(И)=1+1=2.
- N(Е)=N(Ж)=2.
- N(З)=N(Ж)=2.
- N(Д)=N(З)=2.
- N(Г)=N(Ж)+N(З)=2+2=4.
- N(В)=N(Ж)=2.
- N(Б)=N(Е)+N(Ж)=2+2=4.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=4+2+4+2=12.
Ответ: 12.
Считаем количество путей с конца.
- N(К)=1.
- N(И)=N(К)=1.
- N(Ж)=N(К)+N(И)=1+1=2.
- N(Е)=N(Ж)=2.
- N(З)=N(Ж)=2.
- N(Д)=N(З)=2.
- N(Г)=N(Ж)+N(З)=2+2=4.
- N(В)=N(Ж)=2.
- N(Б)=N(Е)+N(Ж)=2+2=4.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=4+2+4+2=12.
Ответ: 12.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| А | Д |
| Б | В |
| Б | Е |
| Б | Ж |
| В | Ж |
| Г | Ж |
| Г | З |
| Д | З |
| Е | Ж |
| З | Ж |
| Ж | И |
| Ж | К |
| И | К |
Сколько существует различных путей из города А в город К?
Считаем количество путей с конца.
- N(К)=1.
- N(И)=N(К)=1.
- N(Ж)=N(К)+N(И)=1+1=2.
- N(Е)=N(Ж)=2.
- N(З)=N(Ж)=2.
- N(Д)=N(З)=2.
- N(Г)=N(Ж)+N(З)=2+2=4.
- N(В)=N(Ж)=2.
- N(Б)=N(В)+N(Е)+N(Ж)=2+2+2=6.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=6+2+4+2=14.
Ответ: 14.
Считаем количество путей с конца.
- N(К)=1.
- N(И)=N(К)=1.
- N(Ж)=N(К)+N(И)=1+1=2.
- N(Е)=N(Ж)=2.
- N(З)=N(Ж)=2.
- N(Д)=N(З)=2.
- N(Г)=N(Ж)+N(З)=2+2=4.
- N(В)=N(Ж)=2.
- N(Б)=N(В)+N(Е)+N(Ж)=2+2+2=6.
- N(А)=N(Б)+N(В)+N(Г)+N(Д)=6+2+4+2=14.
Ответ: 14.
На схеме дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| Б | Д |
| Б | Е |
| В | Е |
| В | Ж |
| Г | Ж |
| Д | З |
| Е | З |
| Е | И |
| Ж | И |
| З | К |
| И | К |
Сколько существует различных путей из города А в город К?
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 = 1.
- N(Е) = N(Б)=1 + N(В)=1 = 2.
- N(Ж) = N(В)=1 + N(Г)=1 = 2.
- N(З) = N(Д)=1 + N(Е)=2 = 3.
- N(И) = N(Е)=2 + N(Ж)=2 = 4.
- N(К) = N(З)=3 + N(И)=4 = 7.
В город К приходит 7 путей.
Ответ: 7.
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 = 1.
- N(Е) = N(Б)=1 + N(В)=1 = 2.
- N(Ж) = N(В)=1 + N(Г)=1 = 2.
- N(З) = N(Д)=1 + N(Е)=2 = 3.
- N(И) = N(Е)=2 + N(Ж)=2 = 4.
- N(К) = N(З)=3 + N(И)=4 = 7.
В город К приходит 7 путей.
Ответ: 7.
На схеме дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| Б | Г |
| Б | Д |
| В | Д |
| В | Е |
| Г | Ж |
| Д | Ж |
| Е | Ж |
| Г | К |
| Ж | К |
Сколько существует различных путей из города А в город К?
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(Б)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(В)=1 = 1.
- N(Ж) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
- N(К) = N(Г)=1 + N(Ж)=4 = 5.
В город К приходит 5 путей.
Ответ: 5.
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(Б)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(В)=1 = 1.
- N(Ж) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
- N(К) = N(Г)=1 + N(Ж)=4 = 5.
В город К приходит 5 путей.
Ответ: 5.
На схеме дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| Б | Д |
| Б | Е |
| В | Д |
| В | Ж |
| Г | Ж |
| Д | З |
| Е | З |
| Ж | З |
| З | К |
| Е | К |
Сколько существует различных путей из города А в город К?
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(Б)=1 = 1.
- N(Ж) = N(В)=1 + N(Г)=1 = 2.
- N(З) = N(Д)=2 + N(Е)=1 + N(Ж)=2 = 5.
- N(К) = N(З)=5 + N(Е)=1 = 6.
В город К приходит 6 путей.
Ответ: 6.
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(Б)=1 = 1.
- N(Ж) = N(В)=1 + N(Г)=1 = 2.
- N(З) = N(Д)=2 + N(Е)=1 + N(Ж)=2 = 5.
- N(К) = N(З)=5 + N(Е)=1 = 6.
В город К приходит 6 путей.
Ответ: 6.
На схеме дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Стрелки на схеме заданы в таблице.
| Откуда | Куда |
|---|---|
| А | Б |
| А | В |
| А | Г |
| Б | Д |
| В | Д |
| В | Е |
| Г | Е |
| Д | Ж |
| Е | Ж |
| Д | И |
| Ж | И |
Сколько существует различных путей из города А в город И?
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(В)=1 + N(Г)=1 = 2.
- N(Ж) = N(Д)=2 + N(Е)=2 = 4.
- N(И) = N(Д)=2 + N(Ж)=4 = 6.
В город И приходит 6 путей.
Ответ: 6.
Посчитаем количество путей динамически: в каждую вершину записываем сумму количеств путей во всех вершинах, из которых в неё входят стрелки.
- N(Б) = N(А)=1 = 1.
- N(В) = N(А)=1 = 1.
- N(Г) = N(А)=1 = 1.
- N(Д) = N(Б)=1 + N(В)=1 = 2.
- N(Е) = N(В)=1 + N(Г)=1 = 2.
- N(Ж) = N(Д)=2 + N(Е)=2 = 4.
- N(И) = N(Д)=2 + N(Ж)=4 = 6.
В город И приходит 6 путей.
Ответ: 6.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 25 | 5 | 5 | ||
| B | 10 | 15 | |||
| C | 25 | 10 | 30 | ||
| D | 5 | 15 | 30 | 20 | |
| E | 5 | 20 |
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Заметим, что C не связан напрямую с E, поэтому путь обязательно должен пройти через другие пункты. Переберём все пути из A в E через C:
- A → C → B → D → E: 25 + 10 + 15 + 20 = 70
- A → C → D → E: 25 + 30 + 20 = 75
Других путей, проходящих через C и заканчивающихся в E, нет (C не соединён с E напрямую, а B не соединён с E).
Ответ: 70.
Заметим, что C не связан напрямую с E, поэтому путь обязательно должен пройти через другие пункты. Переберём все пути из A в E через C:
- A → C → B → D → E: 25 + 10 + 15 + 20 = 70
- A → C → D → E: 25 + 30 + 20 = 75
Других путей, проходящих через C и заканчивающихся в E, нет (C не соединён с E напрямую, а B не соединён с E).
Ответ: 70.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 3 | 7 | 4 | 18 | |
| B | 3 | 3 | |||
| C | 7 | 3 | 5 | 12 | |
| D | 4 | 5 | 6 | ||
| E | 18 | 12 | 6 |
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Возможные пути через C:
- A → B → C → D → E: 3 + 3 + 5 + 6 = 17
- A → C → D → E: 7 + 5 + 6 = 18
- A → B → C → E: 3 + 3 + 12 = 18
- A → C → E: 7 + 12 = 19
- A → D → C → E: 4 + 5 + 12 = 21
Ответ: 17.
Возможные пути через C:
- A → B → C → D → E: 3 + 3 + 5 + 6 = 17
- A → C → D → E: 7 + 5 + 6 = 18
- A → B → C → E: 3 + 3 + 12 = 18
- A → C → E: 7 + 12 = 19
- A → D → C → E: 4 + 5 + 12 = 21
Ответ: 17.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 15 | 13 | 7 | ||
| B | 15 | 3 | |||
| C | 13 | 3 | 2 | 5 | |
| D | 2 | 2 | |||
| E | 7 | 5 | 2 |
Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Возможные пути:
- A → E → D → C → B: 7 + 2 + 2 + 3 = 14
- A → B: 15
- A → E → C → B: 7 + 5 + 3 = 15
- A → C → B: 13 + 3 = 16
Ответ: 14.
Возможные пути:
- A → E → D → C → B: 7 + 2 + 2 + 3 = 14
- A → B: 15
- A → E → C → B: 7 + 5 + 3 = 15
- A → C → B: 13 + 3 = 16
Ответ: 14.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 8 | 3 | 19 | ||
| B | 22 | 11 | |||
| C | 8 | 22 | 9 | 10 | |
| D | 3 | 9 | |||
| E | 19 | 11 | 10 |
Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Возможные пути:
- A → C → E → B: 8 + 10 + 11 = 29
- A → C → B: 8 + 22 = 30
- A → E → B: 19 + 11 = 30
- A → D → C → E → B: 3 + 9 + 10 + 11 = 33
- A → D → C → B: 3 + 9 + 22 = 34
Ответ: 29.
Возможные пути:
- A → C → E → B: 8 + 10 + 11 = 29
- A → C → B: 8 + 22 = 30
- A → E → B: 19 + 11 = 30
- A → D → C → E → B: 3 + 9 + 10 + 11 = 33
- A → D → C → B: 3 + 9 + 22 = 34
Ответ: 29.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 4 | 12 | 16 | ||
| B | 4 | 5 | |||
| C | 12 | 5 | 16 | 6 | |
| D | 16 | 7 | |||
| E | 16 | 6 | 7 |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в D:
- A → B → C → E → D: 4 + 5 + 6 + 7 = 22
- A → E → D: 16 + 7 = 23
- A → B → C → D: 4 + 5 + 16 = 25
- A → C → E → D: 12 + 6 + 7 = 25
- A → C → D: 12 + 16 = 28
Кратчайший путь: A → B → C → E → D = 22.
Ответ: 22.
Переберём все пути из A в D:
- A → B → C → E → D: 4 + 5 + 6 + 7 = 22
- A → E → D: 16 + 7 = 23
- A → B → C → D: 4 + 5 + 16 = 25
- A → C → E → D: 12 + 6 + 7 = 25
- A → C → D: 12 + 16 = 28
Кратчайший путь: A → B → C → E → D = 22.
Ответ: 22.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 10 | 20 | 20 | ||
| B | 10 | 10 | |||
| C | 20 | 10 | 9 | 1 | |
| D | 9 | 7 | |||
| E | 20 | 1 | 7 |
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в D:
- A → E → D: 20 + 7 = 27
- A → B → C → E → D: 10 + 10 + 1 + 7 = 28
- A → C → E → D: 20 + 1 + 7 = 28
- A → C → D: 20 + 9 = 29
- A → B → C → D: 10 + 10 + 9 = 29
Кратчайший путь: A → E → D = 27.
Ответ: 27.
Переберём все пути из A в D:
- A → E → D: 20 + 7 = 27
- A → B → C → E → D: 10 + 10 + 1 + 7 = 28
- A → C → E → D: 20 + 1 + 7 = 28
- A → C → D: 20 + 9 = 29
- A → B → C → D: 10 + 10 + 9 = 29
Кратчайший путь: A → E → D = 27.
Ответ: 27.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | 10 | 5 | 19 | ||
| B | 3 | 2 | ||||
| C | 10 | 2 | 2 | 7 | ||
| D | 5 | 2 | 2 | |||
| E | 2 | 2 | ||||
| F | 19 | 7 | 2 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в F, проходящие через C:
- A → B → C → D → E → F: 3 + 2 + 2 + 2 + 2 = 11
- A → B → C → F: 3 + 2 + 7 = 12
- A → D → C → F: 5 + 2 + 7 = 14
- A → C → D → E → F: 10 + 2 + 2 + 2 = 16
- A → C → F: 10 + 7 = 17
Кратчайший путь: A → B → C → D → E → F = 11.
Ответ: 11.
Переберём все пути из A в F, проходящие через C:
- A → B → C → D → E → F: 3 + 2 + 2 + 2 + 2 = 11
- A → B → C → F: 3 + 2 + 7 = 12
- A → D → C → F: 5 + 2 + 7 = 14
- A → C → D → E → F: 10 + 2 + 2 + 2 = 16
- A → C → F: 10 + 7 = 17
Кратчайший путь: A → B → C → D → E → F = 11.
Ответ: 11.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 6 | 10 | 5 | 19 | ||
| B | 6 | 6 | ||||
| C | 10 | 6 | 4 | 6 | ||
| D | 5 | 4 | 2 | |||
| E | 2 | 2 | ||||
| F | 19 | 6 | 2 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в F, проходящие через C:
- A → D → C → F: 5 + 4 + 6 = 15
- A → C → F: 10 + 6 = 16
- A → C → D → E → F: 10 + 4 + 2 + 2 = 18
- A → B → C → F: 6 + 6 + 6 = 18
- A → B → C → D → E → F: 6 + 6 + 4 + 2 + 2 = 20
Кратчайший путь: A → D → C → F = 15.
Ответ: 15.
Переберём все пути из A в F, проходящие через C:
- A → D → C → F: 5 + 4 + 6 = 15
- A → C → F: 10 + 6 = 16
- A → C → D → E → F: 10 + 4 + 2 + 2 = 18
- A → B → C → F: 6 + 6 + 6 = 18
- A → B → C → D → E → F: 6 + 6 + 4 + 2 + 2 = 20
Кратчайший путь: A → D → C → F = 15.
Ответ: 15.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | 4 | 9 | 15 | ||
| B | 3 | 2 | ||||
| C | 4 | 2 | 6 | |||
| D | 6 | 1 | 3 | |||
| E | 9 | 1 | 1 | |||
| F | 15 | 3 | 1 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в F, проходящие через D:
- A → C → D → E → F: 4 + 6 + 1 + 1 = 12
- A → C → D → F: 4 + 6 + 3 = 13
- A → E → D → F: 9 + 1 + 3 = 13
- A → B → C → D → E → F: 3 + 2 + 6 + 1 + 1 = 13
- A → B → C → D → F: 3 + 2 + 6 + 3 = 14
Кратчайший путь: A → C → D → E → F = 12.
Ответ: 12.
Переберём все пути из A в F, проходящие через D:
- A → C → D → E → F: 4 + 6 + 1 + 1 = 12
- A → C → D → F: 4 + 6 + 3 = 13
- A → E → D → F: 9 + 1 + 3 = 13
- A → B → C → D → E → F: 3 + 2 + 6 + 1 + 1 = 13
- A → B → C → D → F: 3 + 2 + 6 + 3 = 14
Кратчайший путь: A → C → D → E → F = 12.
Ответ: 12.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | 4 | 7 | 15 | ||
| B | 3 | 2 | ||||
| C | 4 | 2 | 6 | |||
| D | 6 | 2 | 3 | |||
| E | 7 | 2 | 2 | |||
| F | 15 | 3 | 2 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Переберём все пути из A в F, проходящие через D:
- A → E → D → F: 7 + 2 + 3 = 12
- A → C → D → F: 4 + 6 + 3 = 13
- A → C → D → E → F: 4 + 6 + 2 + 2 = 14
- A → B → C → D → F: 3 + 2 + 6 + 3 = 14
- A → B → C → D → E → F: 3 + 2 + 6 + 2 + 2 = 15
Кратчайший путь: A → E → D → F = 12.
Ответ: 12.
Переберём все пути из A в F, проходящие через D:
- A → E → D → F: 7 + 2 + 3 = 12
- A → C → D → F: 4 + 6 + 3 = 13
- A → C → D → E → F: 4 + 6 + 2 + 2 = 14
- A → B → C → D → F: 3 + 2 + 6 + 3 = 14
- A → B → C → D → E → F: 3 + 2 + 6 + 2 + 2 = 15
Кратчайший путь: A → E → D → F = 12.
Ответ: 12.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. По каждой дороге можно двигаться только в одном направлении.
Сколько существует различных путей из города А в город К?
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(А)=1 + N(Б)=1 + N(В)=1 = 3.
- В Е: N(Е) = N(В)=1 = 1.
- В И: N(И) = N(Г)=1 + N(Д)=3 + N(Е)=1 = 5.
- В К: N(К) = N(И)=5 = 5.
Число путей из А в К равно 5.
Ответ: 5.
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(А)=1 + N(Б)=1 + N(В)=1 = 3.
- В Е: N(Е) = N(В)=1 = 1.
- В И: N(И) = N(Г)=1 + N(Д)=3 + N(Е)=1 = 5.
- В К: N(К) = N(И)=5 = 5.
Число путей из А в К равно 5.
Ответ: 5.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. По каждой дороге можно двигаться только в одном направлении.
Сколько существует различных путей из города А в город К?
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 = 1.
- В И: N(И) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
- В К: N(К) = N(И)=4 = 4.
Число путей из А в К равно 4.
Ответ: 4.
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 = 1.
- В И: N(И) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
- В К: N(К) = N(И)=4 = 4.
Число путей из А в К равно 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении.
Сколько существует различных путей из города А в город К?
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 = 1.
- В К: N(К) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
Число путей из А в К равно 4.
Ответ: 4.
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(Б)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 = 1.
- В К: N(К) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
Число путей из А в К равно 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К?
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(А)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 + N(Г)=1 = 2.
- В К: N(К) = N(Д)=2 + N(Е)=2 = 4.
Число путей из А в К равно 4.
Ответ: 4.
Подсчитаем количество путей из А в каждую вершину методом динамического программирования: для каждой вершины — сумма чисел путей в предшественников.
- В А приходит 1 путь.
- В Б: N(Б) = N(А)=1 = 1.
- В В: N(В) = N(А)=1 = 1.
- В Г: N(Г) = N(А)=1 = 1.
- В Д: N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е: N(Е) = N(В)=1 + N(Г)=1 = 2.
- В К: N(К) = N(Д)=2 + N(Е)=2 = 4.
Число путей из А в К равно 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении.
Сколько существует различных путей из города А в город З, проходящих через город Д?
Путь из А в З через Д состоит из двух частей.
Количество путей из А в Д равно 3.
Количество путей из Д в З равно 2.
По правилу умножения общее число путей: 3 · 2 = 6.
Ответ: 6.
Путь из А в З через Д состоит из двух частей.
Количество путей из А в Д равно 3.
Количество путей из Д в З равно 2.
По правилу умножения общее число путей: 3 · 2 = 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Ж, проходящих через город Г?
Путь из А в Ж через Г состоит из двух частей.
Количество путей из А в Г равно 3.
Количество путей из Г в Ж равно 2.
По правилу умножения общее число путей: 3 · 2 = 6.
Ответ: 6.
Путь из А в Ж через Г состоит из двух частей.
Количество путей из А в Г равно 3.
Количество путей из Г в Ж равно 2.
По правилу умножения общее число путей: 3 · 2 = 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город З, проходящих через город Д?
Путь из А в З через Д состоит из двух частей: путь из А в Д и путь из Д в З. Найдём количество путей каждого участка отдельно.
Количество путей из А в Д равно 3.
Количество путей из Д в З равно 2.
По правилу умножения общее число путей из А в З через Д равно 3 · 2 = 6.
Ответ: 6.
Путь из А в З через Д состоит из двух частей: путь из А в Д и путь из Д в З. Найдём количество путей каждого участка отдельно.
Количество путей из А в Д равно 3.
Количество путей из Д в З равно 2.
По правилу умножения общее число путей из А в З через Д равно 3 · 2 = 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город З, проходящих через город Г?
Путь из А в З через Г состоит из двух частей: путь из А в Г и путь из Г в З. Найдём количество путей каждого участка отдельно.
Количество путей из А в Г равно 3.
Количество путей из Г в З равно 3.
По правилу умножения общее число путей из А в З через Г равно 3 · 3 = 9.
Ответ: 9.
Путь из А в З через Г состоит из двух частей: путь из А в Г и путь из Г в З. Найдём количество путей каждого участка отдельно.
Количество путей из А в Г равно 3.
Количество путей из Г в З равно 3.
По правилу умножения общее число путей из А в З через Г равно 3 · 3 = 9.
Ответ: 9.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Ж, проходящих через город Г?
Путь из А в Ж через Г состоит из двух частей: путь из А в Г и путь из Г в Ж. Найдём количество путей каждого участка отдельно.
Количество путей из А в Г равно 2.
Количество путей из Г в Ж равно 2.
По правилу умножения общее число путей из А в Ж через Г равно 2 · 2 = 4.
Ответ: 4.
Путь из А в Ж через Г состоит из двух частей: путь из А в Г и путь из Г в Ж. Найдём количество путей каждого участка отдельно.
Количество путей из А в Г равно 2.
Количество путей из Г в Ж равно 2.
По правилу умножения общее число путей из А в Ж через Г равно 2 · 2 = 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город И?
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б. N(Г) = N(Б)=1 = 1.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: В. N(Е) = N(В)=1 = 1.
- В Ж приходят пути из: Г, Д. N(Ж) = N(Г)=1 + N(Д)=2 = 3.
- В З приходят пути из: Д, Е. N(З) = N(Д)=2 + N(Е)=1 = 3.
- В И приходят пути из: Ж, З. N(И) = N(Ж)=3 + N(З)=3 = 6.
Получаем, что число путей из А в И равно 6.
Ответ: 6.
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б. N(Г) = N(Б)=1 = 1.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: В. N(Е) = N(В)=1 = 1.
- В Ж приходят пути из: Г, Д. N(Ж) = N(Г)=1 + N(Д)=2 = 3.
- В З приходят пути из: Д, Е. N(З) = N(Д)=2 + N(Е)=1 = 3.
- В И приходят пути из: Ж, З. N(И) = N(Ж)=3 + N(З)=3 = 6.
Получаем, что число путей из А в И равно 6.
Ответ: 6.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Ж?
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б. N(Г) = N(Б)=1 = 1.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: В. N(Е) = N(В)=1 = 1.
- В Ж приходят пути из: Г, Д, Е. N(Ж) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
Получаем, что число путей из А в Ж равно 4.
Ответ: 4.
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б. N(Г) = N(Б)=1 = 1.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: В. N(Е) = N(В)=1 = 1.
- В Ж приходят пути из: Г, Д, Е. N(Ж) = N(Г)=1 + N(Д)=2 + N(Е)=1 = 4.
Получаем, что число путей из А в Ж равно 4.
Ответ: 4.
На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Е?
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б, В. N(Г) = N(Б)=1 + N(В)=1 = 2.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: Г, Д. N(Е) = N(Г)=2 + N(Д)=2 = 4.
Получаем, что число путей из А в Е равно 4.
Ответ: 4.
Будем считать количество путей из А в каждую из вершин методом динамического программирования. В каждой вершине запишем сумму чисел во всех предыдущих вершинах, из которых ведут стрелки в эту.
- В А приходит 1 путь (это сам А).
- В Б приходят пути из: А. N(Б) = N(А)=1 = 1.
- В В приходят пути из: А. N(В) = N(А)=1 = 1.
- В Г приходят пути из: Б, В. N(Г) = N(Б)=1 + N(В)=1 = 2.
- В Д приходят пути из: Б, В. N(Д) = N(Б)=1 + N(В)=1 = 2.
- В Е приходят пути из: Г, Д. N(Е) = N(Г)=2 + N(Д)=2 = 4.
Получаем, что число путей из А в Е равно 4.
Ответ: 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Н, проходящих через город И?
Для нахождения количества путей из города А в город Н, проходящих через город И, надо найти количество путей из города А в город И, количество путей из города И в город Н, и перемножить получившиеся числа.
Найдём количество путей из А в И:
А = 1. Б = А = 1. В = А = 1. Г = А = 1. Д = Б = 1. Е = Б + В = 2. Ж = В + Г = 2. З = Д + Е = 3. И = Е + Ж + З = 2 + 2 + 3 = 7.
Найдём количество путей из И в Н (при этом И является исходным пунктом):
И = 1. Л = И = 1. М = И = 1. Н = Л + М = 1 + 1 = 2.
Тогда количество путей из А в Н, проходящих через И, равно 7 · 2 = 14.
Ответ: 14.
Для нахождения количества путей из города А в город Н, проходящих через город И, надо найти количество путей из города А в город И, количество путей из города И в город Н, и перемножить получившиеся числа.
Найдём количество путей из А в И:
А = 1. Б = А = 1. В = А = 1. Г = А = 1. Д = Б = 1. Е = Б + В = 2. Ж = В + Г = 2. З = Д + Е = 3. И = Е + Ж + З = 2 + 2 + 3 = 7.
Найдём количество путей из И в Н (при этом И является исходным пунктом):
И = 1. Л = И = 1. М = И = 1. Н = Л + М = 1 + 1 = 2.
Тогда количество путей из А в Н, проходящих через И, равно 7 · 2 = 14.
Ответ: 14.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?
Для нахождения количества путей из города А в город М, проходящих через город Ж, надо найти количество путей из города А в город Ж, количество путей из города Ж в город М, и перемножить получившиеся числа.
Найдём количество путей из А в Ж:
А = 1. Б = А = 1. В = А = 1. Г = Б = 1. Д = Б + В = 2. Е = В = 1. Ж = Г + Д + Е = 1 + 2 + 1 = 4.
Найдём количество путей из Ж в М (при этом Ж является исходным пунктом):
Ж = 1. З = Ж = 1. И = Ж = 1. К = Ж = 1. Л = З + И = 1 + 1 = 2. М = И + К + Л = 1 + 1 + 2 = 4.
Тогда количество путей из А в М, проходящих через Ж, равно 4 · 4 = 16.
Ответ: 16.
Для нахождения количества путей из города А в город М, проходящих через город Ж, надо найти количество путей из города А в город Ж, количество путей из города Ж в город М, и перемножить получившиеся числа.
Найдём количество путей из А в Ж:
А = 1. Б = А = 1. В = А = 1. Г = Б = 1. Д = Б + В = 2. Е = В = 1. Ж = Г + Д + Е = 1 + 2 + 1 = 4.
Найдём количество путей из Ж в М (при этом Ж является исходным пунктом):
Ж = 1. З = Ж = 1. И = Ж = 1. К = Ж = 1. Л = З + И = 1 + 1 = 2. М = И + К + Л = 1 + 1 + 2 = 4.
Тогда количество путей из А в М, проходящих через Ж, равно 4 · 4 = 16.
Ответ: 16.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город З?
Для нахождения количества путей из города А в город Л, проходящих через город З, надо найти количество путей из города А в город З, количество путей из города З в город Л, и перемножить получившиеся числа.
Найдём количество путей из А в З:
А = 1. Б = А = 1. В = А = 1. Г = А = 1. Д = Б = 1. Е = Б + В + Г = 3. Ж = Г = 1. З = Д + Е + Ж = 1 + 3 + 1 = 5.
Найдём количество путей из З в Л (при этом З является исходным пунктом):
З = 1. И = З = 1. К = З = 1. Л = И + К = 1 + 1 = 2.
Тогда количество путей из А в Л, проходящих через З, равно 5 · 2 = 10.
Ответ: 10.
Для нахождения количества путей из города А в город Л, проходящих через город З, надо найти количество путей из города А в город З, количество путей из города З в город Л, и перемножить получившиеся числа.
Найдём количество путей из А в З:
А = 1. Б = А = 1. В = А = 1. Г = А = 1. Д = Б = 1. Е = Б + В + Г = 3. Ж = Г = 1. З = Д + Е + Ж = 1 + 3 + 1 = 5.
Найдём количество путей из З в Л (при этом З является исходным пунктом):
З = 1. И = З = 1. К = З = 1. Л = И + К = 1 + 1 = 2.
Тогда количество путей из А в Л, проходящих через З, равно 5 · 2 = 10.
Ответ: 10.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б = 1; Е = Б + В = 1 + 1 = 2; Ж = В + Г = 1 + 1 = 2; З = Д = 1; И = Д + Е + Ж = 1 + 2 + 2 = 5; К = Ж = 2; Л = З + И = 1 + 5 = 6; М = И + К + Л = 5 + 2 + 6 = 13.
Ответ: 13.
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б = 1; Е = Б + В = 1 + 1 = 2; Ж = В + Г = 1 + 1 = 2; З = Д = 1; И = Д + Е + Ж = 1 + 2 + 2 = 5; К = Ж = 2; Л = З + И = 1 + 5 = 6; М = И + К + Л = 5 + 2 + 6 = 13.
Ответ: 13.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б + В = 1 + 1 = 2; Е = Б + В + Г = 1 + 1 + 1 = 3; Ж = Г = 1; З = Д + Е = 2 + 3 = 5; И = Е + Ж + З = 3 + 1 + 5 = 9.
Ответ: 9.
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б + В = 1 + 1 = 2; Е = Б + В + Г = 1 + 1 + 1 = 3; Ж = Г = 1; З = Д + Е = 2 + 3 = 5; И = Е + Ж + З = 3 + 1 + 5 = 9.
Ответ: 9.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б + В = 1 + 1 = 2; Е = В + Г = 1 + 1 = 2; Ж = Г = 1; З = Д + Е + Ж = 2 + 2 + 1 = 5; И = Е + З = 2 + 5 = 7; К = Ж + З + И = 1 + 5 + 7 = 13.
Ответ: 13.
Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в X. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1; Б = А = 1; В = А = 1; Г = А = 1; Д = Б + В = 1 + 1 = 2; Е = В + Г = 1 + 1 = 2; Ж = Г = 1; З = Д + Е + Ж = 2 + 2 + 1 = 5; И = Е + З = 2 + 5 = 7; К = Ж + З + И = 1 + 5 + 7 = 13.
Ответ: 13.