В графе n вершин каждое неориентированное ребро существует независимо с вероятностью p. Для фиксированных u≠v найдите…
Quant ResearchУровень: ПрактикаRandom graph connection
В графе n вершин каждое неориентированное ребро существует независимо с вероятностью p. Для фиксированных u≠v найдите вероятность хотя бы одного пути u-w-v из двух рёбер.
Подсказки
- Возьмите дополнение: ни один посредник не соединяет концы.
- Проверьте независимость наборов рёбер.
Ответ
Каждая из n-2 промежуточных вершин даёт путь с вероятностью p². Для разных посредников рёбра не пересекаются, поэтому события независимы. Ответ 1-(1-p²)^(n-2).
Источник и лицензия: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · ответ: редакция Quantoros · перевод: Quantoros