桥 (图论)
外观
此条目需要扩充。 (2015年9月17日) |
此条目需要补充更多来源。 (2015年9月17日) |
在图论中,一条边被称为“桥”代表这条边一旦被删除,这张图的连通块数量会增加。[1] 等价地说,一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。
树和森林
[编辑]一张 个点的图最多有 座桥,因为再加一条边就一定会产生一个环。恰好有 座桥的图就是树;而图上每一条边都是桥的图就是森林。
无桥图
[编辑]一个无桥图就是一个没有桥存在的图。等价条件是每个图中的连通分支都拥有一个张开的耳状分解,[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).
- ^ 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 .
- ^ 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.