桥 (图论)

在图论中，一条边被称为“桥”代表这条边一旦被删除，这张图的连通块数量会增加。^[1] 等价地说，一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。

这是有16个顶点和6个桥的图（桥以红色线段标示）

没有桥的无向连通图

树和森林

一张 ${\displaystyle n}$ 个点的图最多有 ${\displaystyle n-1}$ 座桥，因为再加一条边就一定会产生一个环。恰好有 ${\displaystyle n-1}$ 座桥的图就是树；而图上每一条边都是桥的图就是森林。

无桥图

一个无桥图就是一个没有桥存在的图。等价条件是每个图中的连通分支都拥有一个张开的耳状分解，^[2]其中每个连通分支都是2-边连通图，即（根据Robbins定理）每个连通分支都具有强定向性。^[2]

Tarjan的找桥算法

罗伯特·塔扬在 1974 年发表了第一个线性时间的找桥算法^[3]。它的步骤如下：

• 在图 ${\displaystyle G}$ 上找一个生成树 ${\displaystyle F}$
• 用先序遍历走过 ${\displaystyle F}$ 并将每个节点编号。父节点的编号必须比子节点来得小。
• 以后序遍历的顺序处理每个节点 ${\displaystyle v}$ ：
  • 计算 ${\displaystyle v}$ 的小孩个数 ${\displaystyle ND(v)}$ ，即为 ${\displaystyle v}$ 的每个小孩 ${\displaystyle w}$ 的 ${\displaystyle ND(w)}$ 加总再加 ${\displaystyle 1}$
  • 计算 ${\displaystyle L(v)}$：从 ${\displaystyle v}$ 出发经过若干条 ${\displaystyle v}$ 的子树内的边，再经过一条不在子树内的边，可以走到的最小节点编号。这相当于是下列的最小值：
    • ${\displaystyle v}$ 的每个小孩 ${\displaystyle w}$ 的 ${\displaystyle L(w)}$ 
    • 扣掉 ${\displaystyle F}$ 的边，直接和 ${\displaystyle v}$ 相连的节点编号
  • 类似地，计算 ${\displaystyle H(v)}$ ：从 ${\displaystyle v}$ 出发经过若干条 ${\displaystyle v}$ 的子树内的边，再经过一条不在子树内的边，可以走到的最大节点编号。这相当于是下列的最大值：
    •  ${\displaystyle v}$ 的每个小孩 ${\displaystyle w}$ 的 ${\displaystyle H(w)}$ 
    • 扣掉 ${\displaystyle F}$ 的边，直接和 ${\displaystyle v}$ 相连的节点编号
  • 检查 ${\displaystyle v}$ 的每个小孩 ${\displaystyle w}$ ，若 ${\displaystyle L(w)=w}$ 而且 ${\displaystyle H(w)<w+ND(w)}$ ，则 ${\displaystyle v}$ 到 ${\displaystyle w}$ 的边是一座桥。

注释

1. Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998 [2015-09-17], ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4, （原始内容存档于2018-05-05）.
2. Robbins, H. E., A theorem on graphs, with an application to a problem of traffic control, 美国数学月刊, 1939, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517 .
3. Tarjan, R. Endre, A note on finding the bridges of a graph, Information Processing Letters: 160–161, MR 0349483, doi:10.1016/0020-0190(74)90003-9.