桥 (图论)

一張 ${\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}$ 的邊是一座橋。