Сеть компьютеров АлисаПредлагаю ещё раз потренироваться считать количество путей. НикитаХорошая идея. Чем больше путей между компьютерами, тем выше надёжность сети, т. к., если…
Сеть компьютеров АлисаПредлагаю ещё раз потренироваться считать количество путей. НикитаХорошая идея. Чем больше путей между компьютерами, тем выше надёжность сети, т. к., если прервётся сигнал между одной парой компьютеров, можно будет передать его через другие. Посчитай, сколько существует путей в разные вершины графа. Пример: В вершины S1, S2, S3 — один путь; В вершину S4 — два пути: S2 + S3 = 2. Сколько путей существует из вершины А в вершину S5? S5 = S1 + S4 = Сколько путей существует из вершины А в вершину S6? S6 = S3 + S4 = Сколько путей существует из вершины А в вершину B? B = S5 + S4 + S6 =
Задача описывает граф-цепочку, где число путей к каждому узлу равно сумме путей к узлам, из которых можно попасть в этот узел. Начальные данные: узлы S1, S2 и S3 достижимы из A одним путем каждый. Далее есть переходы:
- S4 из S2 и S3
- S5 из S1 и S4
- S6 из S3 и S4
- B из S5, S4 и S6
Пошагово считаем:
- Пути до S1, S2, S3:
- P(S1) = 1
- P(S2) = 1
- P(S3) = 1
Пути до S4: P(S4) = P(S2) + P(S3) = 1 + 1 = 2
Пути до S5: P(S5) = P(S1) + P(S4) = 1 + 2 = 3
Пути до S6: P(S6) = P(S3) + P(S4) = 1 + 2 = 3
Пути до B: P(B) = P(S5) + P(S4) + P(S6) = 3 + 2 + 3 = 8
Ответы:
- Сколько путей из вершины A в вершину S5? 3 пути
- Сколько путей из вершины A в вершину S6? 3 пути
- Сколько путей из вершины A в вершину B? 8 путей
Коротко о методе: это динамическое программирование по графу; для узла считаем как сумму путей по всем предшественникам, что ведут в этот узел. Если нужна проверка по другой схеме графа, пришлите изображение или схему — поможу пересчитать.
