![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Graph_cut_edges.svg/langzh-640px-Graph_cut_edges.svg.png&w=640&q=50)
桥 (图论)
移除會使圖不連通之邊 / 維基百科,自由的 encyclopedia
在圖論中,一條邊被稱為「橋」代表這條邊一旦被刪除,這張圖的連通塊數量會增加。[1] 等價地說,一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。
樹和森林
此條目需要擴充。 (2015年9月17日) |
此條目需要补充更多来源。 (2015年9月17日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Graph_cut_edges.svg/320px-Graph_cut_edges.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Undirected.svg/125px-Undirected.svg.png)
一張 個點的圖最多有
座橋,因為再加一條邊就一定會產生一個環。恰好有
座橋的圖就是樹;而圖上每一條邊都是橋的圖就是森林。
無橋圖
一個無橋圖就是一個沒有橋存在的圖。等價條件是每個圖中的連通分支都擁有一個張開的耳狀分解,[2]其中每個連通分支都是2-邊連通圖,即(根據Robbins定理)每個連通分支都具有強定向性。[2]
Tarjan的找橋演算法
羅伯特·塔揚在 1974 年發表了第一個線性時間的找橋演算法[3]。它的步驟如下:
- 在圖
上找一個生成树
- 用先序遍歷走過
並將每個節點編號。父節點的編號必須比子節點來得小。
- 以後序遍歷的順序處理每個節點
:
- 計算
的小孩個數
,即為
的每個小孩
的
加總再加
- 計算
:從
出發經過若干條
的子樹內的邊,再經過一條不在子樹內的邊,可以走到的最小節點編號。這相當於是下列的最小值:
的每個小孩
的
- 扣掉
的邊,直接和
相連的節點編號
- 類似地,計算
:從
出發經過若干條
的子樹內的邊,再經過一條不在子樹內的邊,可以走到的最大節點編號。這相當於是下列的最大值:
-
的每個小孩
的
- 扣掉
的邊,直接和
相連的節點編號
-
- 檢查
的每個小孩
,若
而且
,則
到
的邊是一座橋。
- 計算
注释
- Bollobás, Béla, Modern Graph Theory, 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).
- 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
.
- 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.