桥 (图论)

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

這是有16個頂點和6個橋的圖（橋以紅色線段標示）

沒有橋的無向連通圖

樹和森林

一張 ${\displaystyle n}$  個點的圖最多有 ${\displaystyle n-1}$  座橋，因為再加一條邊就一定會產生一個環。恰好有 ${\displaystyle n-1}$  座橋的圖就是樹；而圖上每一條邊都是橋的圖就是森林。

無橋圖

一個無橋圖就是一個沒有橋存在的圖。等價條件是每個圖中的連通分支都擁有一個張開的耳狀分解，^[2]其中每個連通分支都是2-邊連通圖，即（根據Robbins定理）每個連通分支都具有強定向性。^[2]

Tarjan的找橋演算法

羅伯特·塔揚在 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}$  的邊是一座橋。

注释

1. Bollobás, Béla, , Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998 [2015-09-17], ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4, （原始内容存档于2018-05-05） .
2. Robbins, H. E., A theorem on graphs, with an application to a problem of traffic control, 美国数学月刊, 1939, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517   .
3. Tarjan, R. Endre, A note on finding the bridges of a graph, Information Processing Letters: 160–161, MR 0349483, doi:10.1016/0020-0190(74)90003-9 .