环形城市道路网络概率问题求解：连通性与可达性计算

问题背景回顾 #

我们有26个城市构成环形网络：A-B-C-…-Y-Z-A，每条道路独立损毁概率为p，下面一步步拆解两个问题的解法：

a) 计算雨后存在两个城市无法相互抵达的概率 #

要解决这个问题，我们可以先反过来算所有城市都能相互连通的概率，再用1减去这个概率就是目标结果。

对于环形图的连通性，有个核心规律：

• 当0条道路损毁时，整个环完整，所有城市自然连通；
• 当恰好损毁1条道路时，剩下的网络会变成一条线性链（比如断了A-B，就成了B-C-…-Z-A的链），所有城市依然能互相抵达；
• 当损毁≥2条道路时，不管这几条道路是否相邻，都会把环拆成至少两个互不连通的区块（比如断了A-B和C-D，A只能通过Z-Y-…-D连通，B只能通过C连通，A和B就彻底断了）。

所以，图连通的概率是前两种情况的概率之和：

• 损毁0条道路的概率：(1-p)^26（所有道路都完好）
• 恰好损毁1条道路的概率：C(26, 1) * p * (1-p)^25 = 26p(1-p)^25（选1条道路损毁，其余全部完好）

因此，存在两个城市无法抵达的概率为：

1 - (1-p)^26 - 26p(1-p)^25

化简后更简洁的形式：

1 - (1-p)^25 * (1 + 25p)

b) 计算雨后从A到Z可通行的概率 #

A和Z是环形里的相邻节点，有两条独立通行路径：

1. 直接走A-Z的短道路；
2. 绕环走A-B-C-…-Y-Z的长路径（共25条道路）。

我们分两种情况计算概率后相加：

• 情况1：A-Z道路完好：此时直接就能通行，概率为(1-p)；
• 情况2：A-Z道路损毁，但长路径完全畅通：长路径是线性链，只要其中任意一条道路断了，A就没法通过这条路径到Z，所以必须25条道路全部完好。这种情况的概率是p * (1-p)^25（A-Z损毁的概率乘以长路径全好的概率）。

把两种情况的概率相加，得到A到Z可通行的总概率：

(1-p) + p*(1-p)^25

内容的提问来源于stack exchange，提问作者Lucky12456