桥 (图论)

移除會使圖不連通之邊

图论中,一条边被称为“”代表这条边一旦被删除,这张图的连通块数量会增加。[1] 等价地说,一条边是一座桥若且唯若这条边不在任何上。一张图可以有零或多座桥。

这是有16个顶点和6个桥的图(桥以红色线段标示)
没有桥的无向连通图

树和森林 编辑

一张   个点的图最多有   座桥,因为再加一条边就一定会产生一个环。恰好有   座桥的图就是;而图上每一条边都是桥的图就是森林

无桥图 编辑

一个无桥图就是一个没有桥存在的图。等价条件是每个图中的连通分支都拥有一个张开的耳状分解[2]其中每个连通分支都是2-边连通图,即(根据Robbins定理)每个连通分支都具有强定向性。[2]

Tarjan的找桥演算法 编辑

罗伯特·塔扬在 1974 年发表了第一个线性时间的找桥演算法[3]。它的步骤如下:

  • 在图   上找一个生成树  
  • 先序遍历走过   并将每个节点编号。父节点的编号必须比子节点来得小。
  • 以后序遍历的顺序处理每个节点   :
    • 计算   的小孩个数   ,即为   的每个小孩    加总再加  
    • 计算  :从   出发经过若干条   的子树内的边,再经过一条不在子树内的边,可以走到的最小节点编号。这相当于是下列的最小值:
      •   的每个小孩   的   
      • 扣掉   的边,直接和   相连的节点编号
    • 类似地,计算   :从   出发经过若干条   的子树内的边,再经过一条不在子树内的边,可以走到的最大节点编号。这相当于是下列的最大值:
      •    的每个小孩   的   
      • 扣掉   的边,直接和   相连的节点编号
    • 检查   的每个小孩   ,若   而且   ,则   到   的边是一座桥。

注释 编辑

  1. ^ 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) .
  2. ^ 2.0 2.1 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 .