桥 (图论)

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

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

没有桥的无向连通图

树和森林

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

无桥图

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

Tarjan的找桥算法

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

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