桥 (图论)

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

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

罗伯特·塔扬在 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}$  的边是一座桥。