第15讲 路与回路, 图的连通性 主要内容: 1.路与回路. 2.图的连通性.

7.4 路与回路 在图G = (V, E)中, 经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题,这就是路的概念. 1.路 7.4 路与回路 在图G = (V, E)中, 经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题,这就是路的概念. 1.路 Def 对于任意图G = (V, E),

路的起点;终点; 路的长度; 平凡路. 需要注意的是,有向图中的路须按边的方向走,有向图中的路可称为有向路.

有两种特殊的路: 一种是节点不重复的路, 称为路径(path). 一种是边不重复的路, 称为轨迹(trail). 说明 由于图论应用的广泛性, 很多概念存在意义上的差别. 之所以选择“路径”, 它有捷径之意；“轨迹”强调边不重复, 它是(可能多次)走过后留下的痕迹.

Theorem 7-3 在n阶图G = (V, E)中, 若存在从节点v0到vl一条路, 则存在一条从v0到vl一条长度 n - 1的路径. Def 7-14(P206) d(u, v); diam(G).

2.回路 Def 起点与终点相同的(长度 1)路称为回路(circuit),除起点重复一次外, 别的节点均不重复的回路称为圈或环(cycle), 边不重复的回路称为简单回路(closed trail). 除起点重复一次外, 别的节点均不重复的回路在图论中常称为圈(cycle), 有圆圈之意, 在计算机科学中常称为环(cycle), 它有环路、循环的意思, 但不要与是边的环(吊环)混淆了, 因为吊环是长度为1的环,但一般的环不是吊环.

有n个节点的圈称为n阶圈,记为Cn. 在n - 1阶圈Cn-1的内部放置一个节点, 并使之与Cn-1的每个节点邻接, 这样得到的图称为n阶轮图, 记为Wn. 由定义知,长度为0的路不称为回路. 显然,节点v到v的边是一个长度为1的圈. Theorem 7-4 在n阶图G = (V, E)中, 若存在从节点v0到v0一条简单回路, 则存在一条从v0到v0一条长度 n 的圈.

下面的定理很有用. Theorem 7-5 在无向图G = (V, E)中,若任意v V有deg(v)  2,则G中存在圈 . Proof 不妨设G是简单图. 在G中选取一条最长的路径L: v0v1…vl, 由于L是最长路径,与v0邻接的节点必在L上. 由于deg(vi)  2, 存在vi (2  i  l)与v0邻接,则v0v1…viv0是G中的一个圈.

7.5 图的连通性 图的基本性质之一是其连通性,它与图中从节点到节点的路密切相关. 为了讨论方便,先给出 7.5 图的连通性 图的基本性质之一是其连通性,它与图中从节点到节点的路密切相关. 为了讨论方便,先给出 Def 在任何图G = (V, E)中,若从节点u到v存在一条路,则称u可达v (accessible). 由于节点v到v总存在一条长度为0的路, 因此任意节点v可达v自身.

先讨论无向图的连通性. 1.无向图的连通性 Def 设G = (V, E)是无向图, 对于G中任意两个节点u和v均可达, 则称G是连通图(connected graph).

Def 设G = (V, E)是无向图, G中极大的连通子图称为G的连通分支(connected component), 图G的连通分支数记为w(G). 在图7-26(a)中图仅一个连通分支. 在图7-26(b)中图有3个连通分支.

Theorem 设G = (V, E)是无向图, 则G是连通图当且仅当w(G) = 1. 例7-5(P208) G不连通 连通. Hint u, v: (1) u, v在G中不邻接. (2) u, v在G中邻接: 第一种方法:根据定义证明!

Theorem 7-7 去掉简单回路上的边或度为1的节点, 图的连通性不变. 例7-6(P208) 设G = (V, E)是n阶简单无向图, 若对于任意的G中不相邻的节点u和v有deg(u) + deg(v)  n - 1, 则G是连通图. Hint (反证) Theorem 7-7 去掉简单回路上的边或度为1的节点, 图的连通性不变. 第二种方法:反证法!

对于无向连通图,其连通的程度是不同的,有些很“脆弱”,有的则相反. (1)点割集与点连通度κ(G). 2.无向连通图的点连通度与边连通度 对于无向连通图,其连通的程度是不同的,有些很“脆弱”,有的则相反. (1)点割集与点连通度κ(G). Def 设G = (V, E)是连通无向图, W  V, (i) G – W不连通或是1阶图; (ii)删除W的任意真子集均连通, 则称W为G的点割集(cut-set of vertices). “割”是分割、分离、分开的意思, 恰使得G不连通或是1阶图所要去掉的节点集合称为的点割集. 若点割集W = {v},则称v为的割点(cut point)或关节点.(数据结构?)

点割集: {a, b}; {c, d}. κ(G) = 2. 边割集: {e1, e2, e3}. λ(G) = 3.

割点: A; B. κ(G) = 1. 割边: e. λ(G) = 1.

Def 7-20(P209) 根据定义,一个连通无向图的点连通度是使得不连通或为1阶图所要删去的最少的节点个数. 于是,1阶图的点连通度为0,而完全无向图Kn的点连通度为n - 1. 点连通度为2的图G称为2-连通或重连通图(bi-connected graph). 确定一个无向图是否重连通具有重要的意义. 假定无向图的节点表示电话交换站,边表示电话线,则在点连通度为2的通讯网络系统中,一个站发生故障系统仍可正常工作.

(2)边割集与边连通度λ(G). Def 设G = (V, E)是连通无向图且F  E, 若从中删除F的所有边所得到的子图不连通或是平凡图,而删除F的任意真子集都连通,则称F为G的边割集(cut-set of edges). 恰使得G不连通或是平凡图所要去掉的边的集合称为G的边割集. 若边割集F = {e},则称e为的割边或桥(bridge). 例子见上.

Def 7-21(P209) 根据定义, 一个连通无向图G的边连通度是使得G不连通或为平凡图所要删去的最少的边的数目. 下面的定理是H. Whitney在1932年给出的关于点连通度、边连通度及最小度之间的联系的一个结论. Theorem 7-8 设G = (V, E)是连通无向图,则

Proof (1)由于将任意一个节点所关联的边全去掉后都不连通,所以有 (2) 设F是G的恰具有 条边的边割集. 考虑删除F中 条边. 删除后不连通, 显然 若删除后连通, 则存在桥uv = {u, v}. 再删除u或v, 即得知结论成立.

3.有向图的连通性 无向图只有连通与不连通两种情况,而有向图存在多种连通特性. 有向图的连通性分下述3种情形分别讨论. (1)强连通图 Def 设G = (V, E)是有向图, u, v  V均相互可达, 则称G为强连通图(strongly connected digraph). 由定义易知, 下图(a)是一个强连通图. 特别地,平凡图是强连通图.

强连通图 单向连通图 弱连通图. 但反过来均不成立!

Theorem7-9 设G = (V, E)是有向图, 则G强连通当且仅当G中存在一条回路, 它通过所有节点. Def 设G = (V, E)是有向图, G的极大的强连通子图称为G的强连通分支(strongly connected component). (i)子图; (ii)强连通; (iii)极大.

Theorem 7-10 设G = (V, E)是有向图,则G的任意节点都位于且仅位于的一个强连通分支中. Hint 任意节点v本身强连通.

(2)单向连通图 Def 设G = (V, E)是有向图,对于任意u, v  V,从u可达v或者从v可达u,则称G为单向连通图(unilateral connected digraph). 下述定理对确定有向图的单向连通分支是非常有用的. Theorem 7-11 设G = (V, E)是有向图, 则G单向连通当且仅当G中存在一条路,它通过所有节点 .

Def 7-26 设G = (V, E)是有向图, G的极大的单向连通子图称为G的单向连通分支. 无向连通图的节点可以位于不同的单向连通分支中.

(3)弱连通图 Def 7-27 设G = (V, E)是有向图,若不考虑边的方向是一个无向连通图,则称G有向图为弱连通图(weakly connected digraph),简称有向图连通. 例子? 三者之间的关系? Def 7-28 设G = (V, E)是有向图, G的极大的弱连通子图称为G的弱连通分支.