К содержанию
Quantoros

В графе 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

Похожие вопросы