桥 (图论)

在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。

這是有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$ 的邊是一座橋。