桥 (图论)

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

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

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

 Tarjan的找橋演算法 
羅伯特·塔揚在 1974 年發表了第一個線性時間的找橋演算法.。它的步驟如下：
 在圖  上找一個生成树 
 用先序遍歷走過  並將每個節點編號。父節點的編號必須比子節點來得小。
 以後序遍歷的順序處理每個節點  ：
 計算  的小孩個數  ，即為  的每個小孩  的  加總再加 
 計算 ：從  出發經過若干條  的子樹內的邊，再經過一條不在子樹內的邊，可以走到的最小節點編號。這相當於是下列的最小值：
  的每個小孩  的  
 扣掉  的邊，直接和  相連的節點編號
 類似地，計算  ：從  出發經過若干條  的子樹內的邊，再經過一條不在子樹內的邊，可以走到的最大節點編號。這相當於是下列的最大值：
  的每個小孩  的  
 扣掉  的邊，直接和  相連的節點編號
 檢查  的每個小孩  ，若  而且  ，則  到  的邊是一座橋。

 注释 

Category:图论
Category:图的连通性