第 五 章 图 论 (第二部分) 1. 通路 2. 图的连通性.

Presentation on theme: "第 五 章 图 论 (第二部分) 1. 通路 2. 图的连通性."— Presentation transcript:

1 第 五 章 图 论 (第二部分) 1. 通路 2. 图的连通性

2 1. 通路 [定义]通路 pseudo path 设G＝(V，E)是图，v0，vn是G中两点。若G中结点序列v0v1 … vn满足：vi与vi+1相邻(0 i＜n), 则该序列称为从v0到vn的通路。 两个端点相同的通路称为回路（环或圈）。 通路中包含的边数称为该通路的长度。 注意： (1)通路中允许有重复的结点和边。

3 通路举例 A B C D E 通路：ADEBDEA 回路：ACDBCEA 回路：ABCDEA

4 简单通(回)路 [定义]简单通(回)路 各边均不相同的通路称为简单通路。 各边均不相同的回路称为简单回路 简单通路：ADEBD
简单回路：ACDBCEA C D

5 基本通(回)路 [定义]基本通(回)路 结点各不相同的通路称为基本通路。 中间结点各不相同的回路称为基本回路。 基本通路：ACEBD
基本回路：ABCDEA C D

6 有向通(回)路 若通路v0v1 … vn各边是有向边，且vi-1和vi分别是有向边的始点与终点，则称该通路为有向通(回)路。
[定义]有向通(回)路 若通路v0v1 … vn各边是有向边，且vi-1和vi分别是有向边的始点与终点，则称该通路为有向通(回)路。

7 通路定理 [定理]通路定理 在n阶图G中，如果有顶点u到v （u v）的通路，那么u到v必有一条长度小于等于n1的基本通路。

8 通路定理证明 定理：在有n个顶点的图G中，如果有顶点u到v的通路，必有长度不大于n-1的基本通路。 证明：(1)先证明u和v之间存在基本通路
若uv之间的通路P中有相同的顶点，则从P中删除相同顶点之间路径，直到P中没有相同顶点，这样得到的路径为u和v之间的基本通路。 (2) 再证基本通路长度不大于n-1 （反证法）设u和v之间的基本通路的长度≥ｎ。 ∵ 一条边关联两个顶点， ∴长度≥ｎ的基本通路上至少有ｎ＋１个顶点。 ∴至少有两个相同顶点在u和v之间的基本通路上，这与基本通路的性质“任意两个顶点不同”相矛盾。 ∴ 基本通路的长度<= n - 1

9 路径：回路定理 [定理]回路定理 在有n个顶点的图G中，如果有顶点v到自身的通路，那么必定有一条从v到v的长度不大于n的基本回路。

10 连通性定义 [定义]两结点连通(可达) [定义]连通无向图 规定：任意顶点与自身连通。 任意两个顶点都连通的无向图
若u与v之间有通路相连，则称u与v连通（可达）。 规定：任意顶点与自身连通。 [定义]连通无向图 任意两个顶点都连通的无向图 a b c d e f

11 有向图的连通性 强连通的有向图 单向连通的有向图 弱连通的有向图 b c a 任意两个顶点都是互相连通的。
任意两个顶点，至少从一个顶点到另一个是连通的 弱连通的有向图 底图连通的 b c a

12 强连通图性质（补充） 定理：一个有向图G是强连通的当且仅当Ｇ中有一条包含所有顶点至少一次的回路。 证明：
 ： Ｇ中有一条包含所有顶点的回路，显然强连通。/*连通图的定义*/  ：如果 G强连通，G中的顶点为v1，v2，….vn, 设v1到v2路径为P1，v2到v3的路径为P2 ，……， vn到v1 的路为Pn ，将P1， P2，…... Pn连起来，此路是一条包含G中所有顶点的回路。

13 有向图连通性举例 判断下面给出的图是强连通图、单向连通图还是弱连通图。 A B C D E F A B C D E F A B D C E

14 无向图的连通分支 [定义]连通分支（connected component） G [定义]连通图：只有一个连通分支的图。
设图G’ 是无向图G的子图的，如果： (1) G’ 是连通的， (2) G’ 不是任何其它连通子图的真子图（极大性） 则称G’ 是G的连通分支。 G [定义]连通图：只有一个连通分支的图。

15 无向图连通分支举例 例 请指出下图G的连通分支数。 v1 v6 v2 v3 v7 v5 v4 G

16 有向图的连通分支 [定义]强（单向、弱）连通分支 设图G’ 是有向图G的子图的，如果： (1) G’ 是强连通（单向连通、弱连通）的，

17 有向图的连通分支举例 例 请指出下图G的所有强分支、单向分支和弱分支。 G v8 v2 v1 v6 v3 v5 v4 e2 e1 e7 e6
强分支: <{v1,v2,v3,v6},{e1,e2,e5,e6,e7}>、 <{v4},>、<{v5},  >、 <{v7},  >、 <{v8},  >、 单向分支: <{v1,v2,v3,v4,v6},{e1,e2,e3,e5,e6,e7}>、<{v4 ,v5},{e4}>， <{v7,v8},{e8}> 弱分支: <{v1,v2,v3,v4,v5,v6},{e1,e2,e3,e4,e5,e6,e7}>、<{v7 ,v8},{e4}>

18 有向图连通分支举例 请给出下图的所有强分支、单向分支和弱分支
A B C D E F P Q S T 强分支：G[{A}]、G[{E}]、G[{F}]、G[{B}]、G[{C}]、G[{D}] 、 G[{P,Q,S,T}] 单向分支： G[{A,E,F}]、G[{B,C,D}]、G[{A,B,C,D}]、 G[{A,C,D,E}]、G[{P,Q,S,T}] 弱分支：G[{A,B,C,D,E,F}]， G[{P,Q,S,T}]

19 图的连通性：连通性质讨论 若n阶图G的邻接矩阵为A=(aij)n×n，V(G)={v1,v2,…,vn}, 则：
（1）若ａij＝ 1，表明vi到vj有一条边，即vi到vj连通； （2）若ａij＝０，表明vi到vj没有长度为1的通路。 ｂij的值表示G中Ｖi到Ｖj长度为２的通路条数。

20 连通性质讨论(续) [定理] 若G的邻接矩阵为A，则矩阵Ａm的元素bij表示vi到vj长度为ｍ的通路条数。

21 可达矩阵 [定义]可达矩阵 若ｎ阶有向图Ｇ的邻接矩阵为A，令 B = A+A2+…+An-1 +An
将B中不为0的元素改为1，为0的元素不变，修改后所得到的矩阵(bij)nn称为G的可达矩阵。 图G从vi点到vj点有通路当且仅当？ bij = 1

22 图的连通性与可达矩阵 B中元素全为１ B中所有关于主对角线对称 的两个元素中至少一个值为１ B中元素全为１ 有向图的连通性（n1）：
设有向图G的可达矩阵为B (1) Ｇ强连通 (2) Ｇ是单向连通的 无向图的连通性（n1）： 设无向图G的可达矩阵为B Ｇ连通 B中元素全为１ B中所有关于主对角线对称 的两个元素中至少一个值为１ B中元素全为１

23 连通性证明题举例1 [试证]：若ｎ个顶点的无向图G=(V,E)连通，则|E|（ｎ－１）。 证明：(归纳法)
(1)ｎ＝２，由G连通可知: |E|  1=ｎ－１,定理成立。 (2)假设ｎ＝ｋ时,结论成立,即|E|ｋ－1. (3)证法一: 当ｎ＝ｋ＋１时，由递归假设可知:|E|ｋ－1. 任选G中一个结点v 若G-v连通, 则 |V(G-v)|=k,故由递归假设|E(G-v)|ｋ－1; 而由v与G-v至少有一条边相连可知: |E||E(G-v)|+1ｋ; 若G-v不连通,不妨设G-v中有m个连通分支G1,G2,…,Gm,设|V(Gi)|=xi; 显然,对所有i=1,2,3,…,m,都有:xi<k. 由归纳假设可知E(Gi)xi-1,而v与每个连通分支至少有一条边相连,故 E(Gi)m+i=1m(xi-1)= m+i=1mxi-m=i=1mxi=k.

24 连通性证明题举例1(续) (3) 证法二: 显然, 在ｋ＋１个顶点中，不存在孤立顶点，否则，G不连通。即G中所有顶点度数至少为1。
G中所有顶点的度数和≥2k＋２。 进而，由握手定理可知：|E| ≥k+１。 命题得证。 2) 若G中至少存在一个度数为1的顶点，设为v。 令G’=G-v,则G’有k个顶点且G’连通。 根据递归假设E(G’)ｋ－1， 故|E|=E(G’)+v与G’相连的边数k-1+1=k. 命题得证.

25 连通性证明举例2 证明：若G是简单图，设为G的顶点的最小度，若>[|V(G)|/2]-1，则G是连通图。 证明：（反证法）
则G中至少存在两个连通分支，不妨设G中的两个连通分支分别为G1和G2，且|V(G1)||V(G2)|。 则有： |V(G1)|[|V(G)|/2]。 而由G是简单图可知：G1中任意顶点v的度数满足： d(v) |V(G1)|-1 [|V(G)|/2]-1 进而，  d(v) [|V(G)|/2]-1，这与前提条件>[|V(G)|/2]-1矛盾。 因此，G是连通图。

26 连通性证明举例3 设G是n阶无向简单图，若G中任意不同的两个顶点的度数 之和大于等于n – 1，请证明G是连通图。 证明：反证法。
不妨设G有k个连通分支G1，G2，……，Gk ，n1，n2，……，nk是各分支的顶点数。则有： n1 + n2 +…+nk = n 任取u  G1, v  G2。 由G是简单图可知： deg(u) <= n1 – 1 且 deg(v) <= n2 – 1。 因此， deg(u) + deg(v) = n1 – 1 + n2 – 1 <= n – 2 这与题设“任意不同的两个顶点的度数之和大于等于n – 1”矛盾。  G是连通图

27 连通性证明举例4 请证明图G和补图~G中至少有一个连通图。 证明： (1)如果G是连通图，问题得证。 (2) 如果G不是连通图。
任取u, v  ~G，设G的连通分支有G1，G2，……，Gk ① 如果u和v是属于G中不同的连通分支Gi和Gj，则(u, v)  ~G ②如果u和v是属于G中相同的连通分支Gi ，则可在G的另一个连通分支中取一个结点x ，则(u, x)  ~G, (v, x)  ~G。∴ u和v之间在~G中有通路uxv相连。 由u和v的任意性，可知~G是连通的。 综上所述， G和补图~G中至少有一个是连通图。

28 课堂练习 证明：若G是简单图，设为G的顶点的最小度，若k，则G中有长为k的基本通路。

29 课堂练习解答 2. 证明：（反证法） 假设G中不存在长度为k的基本通路。 设P=v1v2…vm为G中最长基本通路。则mk。
2. 证明：（反证法） 假设G中不存在长度为k的基本通路。 设P=v1v2…vm为G中最长基本通路。则mk。 假设vm与V(G)-V(P)中的一个结点相连，不妨设为w，则v1v2…vmw为比P更长的一条基本通路。这与P是G中最长的基本通路相矛盾。 因此，vm结点只能与P上的结点v1,v2 , …,vm-1相连，故d(vm)m-1k-1，进而 d(vm)k-1，这与k矛盾。