查看“︁桥 (图论)”︁的源代码

{{expand|time=2015-09-17T15:32:27+00:00}}
{{refimprove|time=2015-09-17T15:32:27+00:00}}
[[File:Graph_cut_edges.svg|thumb|200x200px|這是有16個[[顶点 (图论)|頂點]]和6個橋的圖（橋以紅色線段標示）]]
[[File:Undirected.svg|thumb|125x125px|沒有橋的無向連通圖]]
在[[图论|圖論]]中，一條邊被稱為「'''橋'''」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。<ref>{{Citation|last = Bollobás|first = Béla|author-link = Béla Bollobás|doi = 10.1007/978-1-4612-0619-4|isbn = 0-387-98488-7|location = New York|mr = 1633290|page = 6|publisher = Springer-Verlag|series = Graduate Texts in Mathematics|title = Modern Graph Theory|url = http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6|volume = 184|year = 1998|accessdate = 2015-09-17|archive-date = 2018-05-05|archive-url = https://web.archive.org/web/20180505093140/https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6}}.</ref> 等價地說，一條邊是一座橋若且唯若這條邊不在任何[[環 (圖論)|環]]上。一張圖可以有零或多座橋。

== 樹和森林 ==
一張 <math>n</math> 個點的圖最多有 <math>n-1</math> 座橋，因為再加一條邊就一定會產生一個環。恰好有 <math>n-1</math> 座橋的圖就是[[树 (图论)|樹]]；而圖上每一條邊都是橋的圖就是[[树 (图论)|森林]]。

== 無橋圖 ==
一個'''無橋圖'''就是一個沒有橋存在的圖。等價條件是每個圖中的[[元件 (圖論)|連通分支]]都擁有一個[[耳狀分解|張開的耳狀分解]]，<ref name="robbins39">{{citation
 | last = Robbins | first = H. E. | authorlink = Herbert Robbins
 | journal = [[美国数学月刊]]
 | pages = 281–283
 | title = A theorem on graphs, with an application to a problem of traffic control
 | volume = 46
 | year = 1939
 | doi=10.2307/2303897| hdl = 10338.dmlcz/101517
 | hdl-access = free
 }}.</ref>其中每個連通分支都是[[k-邊連通圖|2-邊連通圖]]，即（根據[[Robbins定理]]）每個連通分支都具有強定向性。<ref name="robbins39"/>

== Tarjan的找橋演算法 ==
[[羅伯特·塔揚]]在 1974 年發表了第一個[[时间复杂度|線性時間]]的找橋演算法<ref>{{Citation|last = Tarjan|first = R. Endre|author-link = Robert Tarjan|doi = 10.1016/0020-0190(74)90003-9|issue = 6|journal = Information Processing Letters|mr = 0349483|pages = 160–161|title = A note on finding the bridges of a graph|volume = 2}}.</ref>。它的步驟如下：
* 在圖 <math>G</math> 上找一個[[生成树]] <math>F</math>
* 用[[树的遍历|先序遍歷]]走過 <math>F</math> 並將每個節點編號。父節點的編號必須比子節點來得小。
* 以後序遍歷的順序處理每個節點 <math>v</math> ：
** 計算 <math>v</math> 的小孩個數 <math>ND(v)</math> ，即為 <math>v</math> 的每個小孩 <math>w</math> 的 <math>ND(w)</math> 加總再加 <math>1</math>
** 計算 <math>L(v)</math>：從 <math>v</math> 出發經過若干條 <math>v</math> 的子樹內的邊，再經過一條不在子樹內的邊，可以走到的最小節點編號。這相當於是下列的最小值：
*** <math>v</math> 的每個小孩 <math>w</math> 的 <math>L(w)</math> 
*** 扣掉 <math>F</math> 的邊，直接和 <math>v</math> 相連的節點編號
** 類似地，計算 <math>H(v)</math> ：從 <math>v</math> 出發經過若干條 <math>v</math> 的子樹內的邊，再經過一條不在子樹內的邊，可以走到的最大節點編號。這相當於是下列的最大值：
*** <math>v</math> 的每個小孩 <math>w</math> 的 <math>H(w)</math> 
*** 扣掉 <math>F</math> 的邊，直接和 <math>v</math> 相連的節點編號
** 檢查 <math>v</math> 的每個小孩 <math>w</math> ，若 <math>L(w) = w</math> 而且 <math>H(w) <  w + ND(w)</math> ，則 <math>v</math> 到 <math>w</math> 的邊是一座橋。

== 注释 ==
{{Reflist}}

{{图论}}

[[Category:图论]]
[[Category:图的连通性]]