桥 (图论)

维基百科,自由的百科全书
跳转至: 导航搜索
這是有16個頂點和6個橋的圖(橋以紅色線段標示)
沒有橋的無向連通圖

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

樹和森林[编辑]

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

Tarjan的找橋演算法[编辑]

羅伯特·塔揚在 1974 年發表了第一個線性時間的找橋演算法[2]。它的步驟如下:

  • 在圖  上找一個生成森林 
  • 先序遍歷走過  並將每個節點編號。父節點的編號必須比子節點來得小。
  • 以後序遍歷的順序處理每個節點  :
    • 計算 的小孩個數  ,即為  的每個小孩 加總再加
    • 計算 :從  出發經過若干條  的子樹內的邊,再經過一條不在子樹內的邊,可以走到的最小節點編號。這相當於是下列的最小值:
      • 的每個小孩 的  
      • 扣掉 的邊,直接和  相連的節點編號
    • 類似地,計算  :從 出發經過若干條 的子樹內的邊,再經過一條不在子樹內的邊,可以走到的最大節點編號。這相當於是下列的最大值:
    •   的每個小孩 的  
      • 扣掉 的邊,直接和  相連的節點編號
    • 檢查 的每個小孩  ,若  而且  ,則  到  的邊是一座橋。

Notes[编辑]

  1. ^ Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998, ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4 .
  2. ^ 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 .