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