和6個橋的圖（橋以紅色線段標示）]]
在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。
樹和森林
一張 n 個點的圖最多有 n-1 座橋，因為再加一條邊就一定會產生一個環。恰好有 n-1 座橋的圖就是樹；而圖上每一條邊都是橋的圖就是森林。
無橋圖
一個無橋圖就是一個沒有橋存在的圖。等價條件是每個圖中的連通分支都擁有一個張開的耳狀分解，其中每個連通分支都是2-邊連通圖，即（根據Robbins定理）每個連通分支都具有強定向性。。它的步驟如下：
- 在圖 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) ，則 v 到 w 的邊是一座橋。
注释
评论 (0)