跳转到内容

桥 (图论)

维基百科,自由的百科全书
这是有16个顶点和6个桥的图(桥以红色线段标示)
没有桥的无向连通图

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

树和森林

[编辑]

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

无桥图

[编辑]

一个无桥图就是一个没有桥存在的图。等价条件是每个图中的连通分支都拥有一个张开的耳状分解[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 .