顶点对之间具有两条边不相交路径的数量

Question

我目前正在研究一种算法，该算法计算在多图中至少有两个边不相交路径的顶点对的数量。该算法通过查找双连接图可以正常工作，但是当顶点连接两个不同的双连接抓取时，例如在沙漏图中，我遇到了问题。此外，两个顶点之间可能具有尽可能多的不同边。

Answer 1

如果从图形中删除所有桥接边(参见 https://en.wikipedia.org/wiki/Bridge_(graph_theory((，则在每个剩余的连接组件中，每个顶点至少有两个到其他顶点的不相交路径。

此类对的总数是所有 n(n-1(/2 的总和，其中 n 是每个连接组件中的顶点数。