离散数学屈婉玲第九章ppt课件.ppt

《离散数学屈婉玲第九章ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学屈婉玲第九章ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第三部分第三部分 图论图论本部分主要内容本部分主要内容l 图的基本概念图的基本概念l 树树l 欧拉图与哈密顿图欧拉图与哈密顿图l 二部图与匹配二部图与匹配l 平面图平面图l 着色着色2第九章第九章 图的基本概念图的基本概念主要内容主要内容l 图图l 通路与回路通路与回路l 图的连通性图的连通性l 图的矩阵表示图的矩阵表示预备知识预备知识l 多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合l 无序集无序集A B=(x,y) | x A y B14.1 图图定义定义9.1 无向图无向图G = , 其中其中(1) V为非空有穷集为非空有穷集, 称为称为顶点集顶点集，其元素称为，其元素称

2、为顶点顶点(2) E为为V V 的多重有穷集的多重有穷集, 称为称为边集边集, 其元素称为其元素称为无向边无向边, 简简称称边边例例 无向图无向图G = , 其中其中 V = v1, v2, v3, v4, v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 4有向图有向图定义定义9.2 有向图有向图D=,其中其中(1) V 为非空有穷集为非空有穷集, 称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点(2) E为为V V 的多重有穷集的多重有穷集, 称为称为边集边集, 其元素称为其元素称为有向边有向边,

3、 简简称称边边例例 有向图有向图D=, 其中其中V=a,b,c,dE=, , 注意：图的集合表示与图形表示之间的对应注意：图的集合表示与图形表示之间的对应5相关概念相关概念1. 无向图和有向图通称图无向图和有向图通称图. 记顶点集记顶点集V(G), 边集边集E(G). 2. 图的阶图的阶, n阶图阶图.3. n 阶零图阶零图Nn, 平凡图平凡图N1.4. 空图空图.5. 标定图与非标定图标定图与非标定图.6. 有向图的基图有向图的基图.7. 无向图中顶点与边的关联及关联次数无向图中顶点与边的关联及关联次数, 顶点与顶点、边与顶点与顶点、边与 边的相邻关系边的相邻关系.8. 有向图中顶点与边的关

4、联有向图中顶点与边的关联, 顶点与顶点、边与边的相邻关顶点与顶点、边与边的相邻关 系系.9. 环环, 孤立点孤立点.6多重图与简单图多重图与简单图定义定义9.3 无向图中关联同一对顶点的无向图中关联同一对顶点的2条和条和2条以上的边称为条以上的边称为平行边平行边. 有向图中有向图中2条和条和2条以上始点、终点相同的边称为条以上始点、终点相同的边称为平平行边行边. 平行边的条数称为平行边的条数称为重数重数.含平行边的图称为含平行边的图称为多重图多重图, 不含平行边和环的图称为不含平行边和环的图称为简单图简单图.定义定义9.4 设设G=为无向图为无向图, v V, 称称v作为边的端点的次作为边的端

5、点的次数之和为数之和为v的的度数度数, 简称简称度度, 记作记作d(v). 设设D=为有向图为有向图, v V, 称称v作为边的始点的次数之和作为边的始点的次数之和为为v的的出度出度, 记作记作d+(v); 称称v作为边的终点的次数之和为作为边的终点的次数之和为v的的入入度度, 记作记作d (v); 称称d+(v)+d (v)为为v的的度数度数, 记作记作d(v).7顶点的度数顶点的度数设设G=为无向图为无向图, G的的最大度最大度 (G)=maxd(v) | v V G的的最小度最小度 (G)=mind(v) | v V 设设D=为无向图为无向图, D的的最大度最大度 (D)=maxd(v)

6、 | v V D的的最小度最小度 (D)=mind(v) | v V D的的最大出度最大出度 +(D)=maxd+(v) | v V D的的最小出度最小出度 +(D)=mind+(v) | v V D的的最大入度最大入度 (D)=maxd (v) | v V D的的最小入度最小入度 (D)=mind (v) | v V 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点, 悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边.偶度偶度(奇度奇度)顶点顶点: 度数为偶数度数为偶数(奇数奇数)的顶点的顶点8实例实例d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3.

7、 =4, =1.v4是悬挂点是悬挂点, e7是悬挂边是悬挂边. d+(a)=4, d (a)=1, d(a)=5, d+(b)=0, d (b)=3, d(b)=3, d+(c)=2, d (c)=1, d(c)=3, d+(d)=1, d (d)=2, d(d)=3, +=4, +=0, =3, =1, =5, =3.9定理定理9.1 在任何无向图中在任何无向图中, 所有顶点的度数之和等于边数的所有顶点的度数之和等于边数的2倍倍.证证 G中每条边中每条边 (包括环包括环) 均有两个端点，所以在计算均有两个端点，所以在计算G中各顶中各顶点度数之和时，每条边均提供点度数之和时，每条边均提供2度，

8、度，m 条边共提供条边共提供 2m 度度.握手定理握手定理定理定理9.2 在任何有向图中，所有顶点的度数之和等于边数的在任何有向图中，所有顶点的度数之和等于边数的2倍倍; 所有顶点的入度之和等于所有顶点的出度之和所有顶点的入度之和等于所有顶点的出度之和, 都等于边数都等于边数.推论推论 任何图任何图 (无向或有向无向或有向) 中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数.证证 由握手定理由握手定理, 所有顶点的度数之和是偶数所有顶点的度数之和是偶数, 而偶度顶点的度而偶度顶点的度数之和是偶数数之和是偶数, 故奇度顶点的度数之和也是偶数故奇度顶点的度数之和也是偶数. 所以奇度顶所以奇度顶点的

9、个数必是偶数点的个数必是偶数10例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余度顶点，其余均为均为2度顶点度，问度顶点度，问G的阶数的阶数n为几？为几？解解 本题的关键是应用握手定理本题的关键是应用握手定理. 设除设除3度与度与4度顶点外，还有度顶点外，还有x个顶点个顶点, 由握手定理由握手定理, 16 2=32 = 3 4+4 3+2x解得解得 x = 4, 阶数阶数 n = 4+4+3=11. 握手定理应用握手定理应用定理定理9.3 设设G为任意为任意n阶无向简单图，则阶无向简单图，则 (G) n 1图的同构图的同构定义定义9.5 设设G1=, G2

10、=为两个无向图为两个无向图(两个有向两个有向图图)，若存在双射函数，若存在双射函数f:V1V2, 使得使得 vi,vj V1, (vi,vj) E1 当且仅当当且仅当 (f(vi),f(vj) E2 （ E1 当且仅当当且仅当 E2 )并且并且, (vi,vj)（）与）与 (f(vi),f(vj)（）的重数相）的重数相同，则称同，则称G1与与G2是是同构同构的，记作的，记作G1 G2. 例例 12图同构的实例图同构的实例 (1) (2) (3) (4) (1)与与(2), (3)与与(4), (5)与与(6)均不同构均不同构. (5) (6) 说明说明: 1. 图的同构关系具有自反性、对称性和

11、传递性图的同构关系具有自反性、对称性和传递性. 2. 判断两个图同构是个难题判断两个图同构是个难题图同构的实例图同构的实例所有所有4阶阶3条边非同构的简单无向图条边非同构的简单无向图13所有所有3阶阶2条边非同构的简单有向图条边非同构的简单有向图补图补图与自补图与自补图定义定义9.6 设设G=为为n阶无向简单图，令阶无向简单图，令 =(u,v) | u V v V u v (u,v) E,称称 =为为G的的补图补图 若若G 则称则称G是是自补图自补图 EEGG例例 (b)与与(c)互为补图，互为补图，(a)是自补图是自补图15完全图与竞赛图完全图与竞赛图定义定义9.7 (1) n (n 1)

12、阶阶无向完全图无向完全图每个顶点与其余顶点均相邻的每个顶点与其余顶点均相邻的无向简单图，记作无向简单图，记作 Kn.简单性质：简单性质：m=n(n-1)/2, = =n-1(2) n (n 1)阶阶有向完全图有向完全图每对顶点之间均有两条方向相每对顶点之间均有两条方向相反的有向边的有向简单图反的有向边的有向简单图.简单性质：简单性质： m=n(n-1), = =2(n-1) += += = =n-1(3) n (n 1) 阶阶竞赛图竞赛图基图为基图为Kn的有向简单图的有向简单图.简单性质：简单性质： m=n(n-1)/2, = =n-1 正则图正则图 K5 3阶有向完全图阶有向完全图 4阶竞赛

13、图阶竞赛图定义定义9.8 k-正则图正则图 = =k 的无向简单图的无向简单图简单性质：简单性质：m=kn/2, 当当k是奇数时是奇数时, n必为偶数必为偶数.例例 Kn是是 (n 1)-正则图正则图 彼得松图彼得松图是是3-正则图正则图子图子图定义定义9.9 设两个图设两个图G=, G =（同为无向图或（同为无向图或同为有向图）同为有向图）, 若若V V且且EE，则称，则称G 是是G的的子图子图，G为为G 母图母图，记作，记作G G. 又若又若V V或或E E，则称，则称G 为为G的的真真子图子图. 若若G G且且V =V，则称，则称G 为为G的的生成子图生成子图 设设V1 V且且V1, 称

14、以称以V1为顶点集为顶点集, 以以G中两个端点都在中两个端点都在V1中的边组成边集的图为中的边组成边集的图为G中中V1的的导出子图导出子图, 记作记作GV1. 设设E1 E且且E1, 称以称以E1为边集为边集, 以以E1中边关联的顶点为顶点中边关联的顶点为顶点集的图为集的图为G中中E1的的导出子图导出子图, 记作记作GE1例例 G Ga,b,c Ge1,e318定义定义9.10 设设G=为无向图为无向图 (1) 设设e E，用，用G e表示从表示从G中去掉边中去掉边e，称为，称为删除边删除边e又又设设E E，用，用 G E 表示从表示从G中删除中删除E 中的所有边，称为中的所有边，称为删除删除

15、E (2) 设设v V，用，用G v表示从表示从G中去掉中去掉v及所关联的所有边，称及所关联的所有边，称为为删除顶点删除顶点v又设又设V V，用，用G V 表示从表示从G中删除中删除V 中所有中所有的顶点，称为的顶点，称为删除删除V (3) 设设e=(u,v) E，用，用Ge表示从表示从G中删除中删除e后，将后，将e的两个的两个端点端点u,v用一个新的顶点用一个新的顶点w（可以用（可以用u或或v充当充当w）代替，并使）代替，并使w关联除关联除e以外以外u,v关联的所有边，称为关联的所有边，称为收缩边收缩边e (4) 设设u,v V（u,v可能相邻，也可能不相邻），用可能相邻，也可能不相邻），用

16、G (u,v)（或（或G+(u,v)）表示在）表示在u,v之间加一条边之间加一条边(u,v)，称为，称为加新边加新边 在收缩边和加新边过程中可能产生环和平行边在收缩边和加新边过程中可能产生环和平行边 删除删除, 收缩与加新边收缩与加新边19实例实例v1v2v3v4v5e1e2e3e4e5e6e7Gv1v2v3v4v5e1e2e3e4e6e7G-e5v1v2v3v4v5e2e3e5e6e7G-e1,e4v1v2v3v4e3e4e5e6e7G-v5v1v2v3e4e5e7G-v4,v5v1v3v4v5e1e2e3e4e6e7Ge5209.2 通路与回路通路与回路定义定义9.11 设图设图G= (无

17、向或有向的无向或有向的), G中顶点与边的交中顶点与边的交替序列替序列 = v0e1v1e2elvl，如果，如果vi 1, vi 是是 ei 的端点的端点(始点和终始点和终点点), 1 i l, 则称则称 为为v0到到vl的的通路通路. v0,vl分别称作分别称作 的的始点始点和和终终点点. 中的边数中的边数l称作它的称作它的长度长度. 又又若若 v0=vl, 则称则称 为为回路回路. 若若所有的边各异所有的边各异, 则称则称 为为简单通路简单通路. 又若又若v0=vl, 则称则称 为为简单回简单回路路. 若若 中所有顶点各异中所有顶点各异(除除v0和和vl可能相同外可能相同外)且所有边也各且

18、所有边也各异异, 则称则称 为为初级通路初级通路或或路径路径. 若又有若又有v0=vl, 则称则称 为为初级回初级回路路或或圈圈. 长度为奇数的圈称为长度为奇数的圈称为奇圈奇圈, 长度为偶数的圈称为长度为偶数的圈称为偶圈偶圈. 若若 中有边重复出现中有边重复出现, 则则 称为称为复杂通路复杂通路. 若又有若又有v0=vl, 则称则称 为为复杂回路复杂回路.21通路与回路通路与回路定理定理9.4 在在n 阶图阶图G中，若从顶点中，若从顶点u 到到v（u v）存在通路，则）存在通路，则从从u 到到 v 存在长度小于或等于存在长度小于或等于n 1 的通路的通路.推论推论 在在 n 阶图阶图G中，若从

19、顶点中，若从顶点u 到到 v（u v）存在通路，则）存在通路，则从从u 到到v 存在长度小于或等于存在长度小于或等于n 1的初级通路（路径）的初级通路（路径）.定理定理9.5 在在n 阶图阶图G中，若存在中，若存在 v 到自身的回路，则一定存在到自身的回路，则一定存在v 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在在n 阶图阶图G中，若存在中，若存在 v 到自身的简单回路，则一定存到自身的简单回路，则一定存在在v 到自身的长度小于或等于到自身的长度小于或等于n 的初级回路的初级回路.22同构意义下和定义意义下的圈同构意义下和定义意义下的圈例例2 无向完全图无向完全图

20、Kn（n 3）中有几种非同构的圈？）中有几种非同构的圈？ 解解 长度相同的圈都是同构的长度相同的圈都是同构的. 易知易知Kn(n 3)中含长度中含长度3,4,n的圈，共有的圈，共有n 2种非同构的圈种非同构的圈长度相同的圈都是同构的长度相同的圈都是同构的, 因此在因此在同构意义下同构意义下给定长度的圈给定长度的圈只有一个只有一个. 在标定图中在标定图中, 圈表示成顶点和边的标记序列圈表示成顶点和边的标记序列. 如果如果只要两个圈的标记序列不同只要两个圈的标记序列不同, 称这两个圈在称这两个圈在定义意义下定义意义下不同不同.例例3 无向完全图无向完全图K3的顶点依次标定为的顶点依次标定为a,b,

21、c在定义意义下在定义意义下K3中有多少个不同的长度为中有多少个不同的长度为3的圈？的圈？解解 在定义意义下在定义意义下, 不同起点不同起点(终点终点)的圈是不同的的圈是不同的, 顶点间排顶点间排列顺序不同的圈也是不同的列顺序不同的圈也是不同的, 因而因而K3中有中有3!=6个不同的长为个不同的长为3的圈：的圈：abca，acba，bacb，bcab，cabc，cbac23带权图与最短路径带权图与最短路径定义定义9.12 设图设图G= (无向图或有向图无向图或有向图), 对对G的每一条边的每一条边e,给定一个数给定一个数W(e),称作边称作边e的的权权. 把这样的图称为把这样的图称为带权图带权图

22、, 记作记作G=. 当当e=(u,v)()时时, 把把W(e)记作记作W(u,v). 设设P是是G中的一条通路中的一条通路, P中所有边的权之和称为中所有边的权之和称为P的的长度长度,记作记作W(P). 类似地类似地, 可定义回路可定义回路C的长度的长度W(C). 设带权图设带权图G= (无向图或有向图无向图或有向图), 其中每一条边其中每一条边e的的权权W(e)为非负实数为非负实数. u,v V, 当当u和和v连通连通(u可达可达v)时时, 称从称从u到到v长度最短的路径为从长度最短的路径为从u到到v的的最短路径最短路径, 称其长度为从称其长度为从u到到v的的距离距离, 记作记作d(u,v)

23、. 约定约定: d(u,u)=0; 当当u和和v不连通不连通(u不可达不可达v)时时, d(u,v)=+ .24最短路问题最短路问题最短路问题最短路问题: 给定带权图给定带权图G=及顶点及顶点u和和v, 其中每一条其中每一条边边e的权的权W(e)为非负实数为非负实数, 求从求从u到到v的最短路径的最短路径.Dijkstra标号法标号法 (求从求从s到其余各点的最短路径和距离到其余各点的最短路径和距离)1. 令令l(s)(s,0), l(v)(s,+ ) (v V-s), i1, l(s)是永久标号是永久标号, 其余标号均为临时标号其余标号均为临时标号, us2. for 与与u关联的临时标号的

24、顶点关联的临时标号的顶点v 3. if l2(u)+W(u,v) l2(v) then 令令l(v)(u,l2(u)+W(u,v)4. 计算计算l2(t)=min l2(v) | v V且有临时标号且有临时标号, l(t)改为永久标号改为永久标号5. if in then 令令ut, ii+1, 转转2对每一个对每一个u, d(s,u)= l2(u),根据根据l1(v)回溯找到回溯找到s到到u的最短路径的最短路径.25实例实例例例9.5 一个总部和一个总部和6个工地个工地, 求从总部到各工地的最短路径求从总部到各工地的最短路径解解 12345671510364451726总部总部1234567

25、1510364451726 (0,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)26实例实例12345671510364451726 (0,S)(15,1)(10,1)(+ ,S)(+ ,S)(+ ,S)(+ ,S)u=112345671510364451726 (0,S)(13,3)(10,1)(+ ,S)(14,3)(+ ,S)(+ ,S)u=327实例实例12345671510364451726 (0,S)(13,3)(10,1)(19,2)(14,3)(30,2)(+ ,S)u=212345671510364451726 (0,S)(13,3)(10,1)

26、(18,5)(14,3)(30,2)(16,5)u=528实例实例12345671510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=612345671510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=429实例实例v1v3v2, d(v1,v2)=13 v1v3, d(v1,v3)=10v1v3v5v4, d(v1,v4)=18 v1v3v5, d(v1,v5)=14v1v3v5v6, d(v1,v6)=16 v1v3v5v6v7, d(v1,v7)=2212345671

27、510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=7309.3 图的连通性图的连通性定义定义9.13 设无向图设无向图G=，若，若u,v V之间存在通路，则称之间存在通路，则称u,v是是连通的连通的，记作，记作uv. 规定规定: v V vv 若无向图若无向图G是平凡图或是平凡图或G中任何两个顶点都是连通的，则中任何两个顶点都是连通的，则称称G为为连通图连通图，否则称，否则称G为为非连通图非连通图是是V上的等价关系上的等价关系, 具有自反性、对称性和传递性具有自反性、对称性和传递性定义定义9.14 设无向图设无向图G=，Vi是是V关

28、于顶点之间连通关关于顶点之间连通关系的一个等价类，称导出子图系的一个等价类，称导出子图GVi为为G的一个的一个连通分支连通分支. G的的连通分支数连通分支数记为记为p(G)31点割集与边割集点割集与边割集定义定义9.15 设无向图设无向图G=. 若若V V使得使得p(G V )p(G), 且且对于任意的对于任意的V V , 均有均有p(G V )=p(G), 则称则称V 是是G的的点割集点割集.若若V =v, 则称则称v为为割点割点定义定义9.16 设无向图设无向图G=, 若若E E使得使得p(G E )p(G), 且且对于任意的对于任意的E E , 均有均有p(G E )=p(G), 则称则

29、称E 是是G的的边割集边割集，简称为简称为割集割集. 若若E =e, 则称则称e为为割边割边或或桥桥例例3 v1,v4，v6是点割集，是点割集，v6是割点是割点. v2,v5不是不是.e1,e2，e1,e3,e5,e6，e8等等是边割集，是边割集，e8是桥是桥. 而而e7,e9,e5,e6 不是不是.32点连通度与边连通度点连通度与边连通度定义定义9.17 G为连通非完全图为连通非完全图, 称称 (G) = min |V | V 为点割集为点割集 为为G的的点连通度点连通度, 简称简称连通度连通度. 若若 (G) k，则称，则称G为为 k-连通图连通图 . 规定规定 (Kn) = n 1, 非

30、连通图的连通度为非连通图的连通度为0.定义定义9.18 设设G为连通图为连通图, 称称 (G) = min|E | E 为边割集为边割集为为G的的边连通度边连通度. 若若 (G) r，则称，则称G是是 r 边边-连通图连通图. 规定非连通图的边连通度为规定非连通图的边连通度为0.v1v2v3v4v5e1e2e3e4e5e6e7例例 =2, 2-连通图连通图, 也是也是1-连通连通. =2, 2边边-连通图连通图, 也是也是1边边-连通连通.33几点说明几点说明l (Kn)= (Kn)=n 1l G非连通，则非连通，则 = =0l 若若G中有割点，则中有割点，则 =1，若有桥，则，若有桥，则 =

31、1l 若若 (G)=k, 则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1l 若若 (G)=r, 则则G是是1边边-连通图，连通图，2边边-连通图，连通图，r边边-连通连通图，但不是图，但不是(r+s)-边连通图，边连通图，s 1定理定理9.6 (G) (G) (G)34有向图的连通性及分类有向图的连通性及分类定定义义9.19 设设D=为一个有向图为一个有向图, vi,vj V, 若从若从vi到到vj存在存在通路通路, 则称则称vi可达可达vj, 记作记作vivj . 规定规定vi vi. 若若vivj且且vjvi，则称则称v

32、i与与vj是是相互可达相互可达的的, 记作记作vivj. 规定规定vivi性质性质: 具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 定义定义9.20 若有向图若有向图D=V,E)的基图是连通图的基图是连通图, 则称则称D是是弱连通弱连通图图, 简称为简称为连通图连通图. 若若 vi,vj V, vivj与与vjvi至少有一个成立，至少有一个成立，则称则称 D是是单向连通图单向连通图. 若若 vi,vj V, 均有均有vivj, 则称则称D是是强连强连通图通图35有向图的连通性有向图的连通性 强连通强连通 单向连通单向连通 弱连通弱连通

33、定理定理9.7 有向图有向图D=是强连通图当且仅当是强连通图当且仅当D中存在经过中存在经过每个顶点至少一次的回路每个顶点至少一次的回路证证 充分性显然充分性显然. 证必要性证必要性. 设设V=v1,v2,vn, i为为vi到到vi+1的通的通路路( i=1,2,n 1), n为为vn到到v1的通路的通路. 依次连接依次连接 1, 2, , n 1, n所得到的回路经过所得到的回路经过D中每个顶点至少一次中每个顶点至少一次定理定理9.8 有向图有向图D是单向连通图当且仅当是单向连通图当且仅当D中存在经过每个中存在经过每个顶点至少一次的通路顶点至少一次的通路例例扩大路径法扩大路径法设设G=为无向图

34、为无向图, 为为G中一条路径中一条路径. 若此路径的两个端若此路径的两个端点都不与通路外的顶点相邻点都不与通路外的顶点相邻, 则称则称 是是极大路径极大路径.任取一条边任取一条边, 如果它有一个端点与其他的顶点相邻如果它有一个端点与其他的顶点相邻, 就将这条就将这条边延伸到这个顶点边延伸到这个顶点. 继续这一过程继续这一过程, 直至得到一条极大路径为直至得到一条极大路径为止止. 称此种方法为称此种方法为“扩大路径法扩大路径法”. 用扩大路径法总可以得到用扩大路径法总可以得到一条极大路径一条极大路径. 在有向图中可类似讨论在有向图中可类似讨论.例例 由一条路径扩大出的极大路径不惟一，极大路径不一

35、定是由一条路径扩大出的极大路径不惟一，极大路径不一定是最长的路径最长的路径37扩大路径法的应用扩大路径法的应用例例4 设设 G 为为 n（n 3）阶无向简单图，）阶无向简单图， 2，证明，证明G 中存在中存在长度长度 +1 的圈的圈.证证 设设 = v0v1vl 是一条极大路径是一条极大路径, 则则 l . 因为因为v0 不与不与 外外顶点相邻顶点相邻, 又又 d(v0) , 因而在因而在 上除上除 v1外外, 至少还存在至少还存在 1个个顶点与顶点与 v0 相邻相邻. 设设 vx 是离是离 v0 最远的顶点最远的顶点, 于是于是v0v1vxv0 为为 G 中长度中长度 +1 的圈的圈. 38

36、9.4 图的矩阵表示图的矩阵表示无向图的关联矩阵无向图的关联矩阵定义定义9.21 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G). 10000110000011001112)(GM例例39无向图关联矩阵的性质无向图关联矩阵的性质是孤立点是孤立点平行边的列相同平行边的列相同imjijjiijimjijniijvmmmnivdmmjm 0)5()4(2)3(,.,2 , 1,)()2(,.,2 , 1,2)1(1,1140 的的终终点点为为，不不关关联联与与，的的始始点点为为

37、jijijiijevevevm10,1定义定义9.22 设有向图有向图D=中无环，令中无环，令则称则称 (mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D). 例例有向图(无环)的关联矩阵 11100110000011100011)(DM41(1) 每列恰好有一个每列恰好有一个+1和一个和一个-1(2) -1的个数等于的个数等于+1的个数，都等于边数的个数，都等于边数m.(3)第第i行中，行中，+1的个数等于的个数等于d+(vi)，-1的个数等于的个数等于d (vi)(4) 平行边对应的列相同平行边对应的列相同有向图关联矩阵的性质42有向图的邻接矩阵有向图的邻接矩阵定义定义9.23

38、设有向图设有向图D=, V=v1, v2, , vn, 令令 为顶点为顶点 vi 邻接到顶点邻接到顶点 vj 边的条数，称边的条数，称( )为为D的的邻接矩阵邻接矩阵，记作，记作A(D)，或简记为，或简记为A. )1(ija)1(ija 1100100001000120A例例43有向图邻接矩阵的性质有向图邻接矩阵的性质的回路数的回路数中长度为中长度为的通路数的通路数中长度为中长度为1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 定理定理9.9 设设 A为有向图为有向图 D

39、 的邻接矩阵的邻接矩阵, 顶点集顶点集V=v1,v2, vn，则则 A 的的 l 次幂次幂 Al（l 1）中元素）中元素推论推论 设设Bl=A+A2+Al (l 1), 则则 ninjlijb11)( niliib1)(为长度小于或等于为长度小于或等于 l 的回路数的回路数.为长度小于或等于为长度小于或等于 l 的通路数的通路数, 邻接矩阵的应用邻接矩阵的应用为长度为 l 的通路总数，)(lija)(liia ninjlija11)( niliia1)(为vi 到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为长度为为长度为 l 的回路总数的回路总数. 45例例5 有向图有向图D

40、如图所示，求如图所示，求 A, A2, A3, A4，并回答诸问题：，并回答诸问题：(1) D 中长度为中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多的通路各有多少条？其中回路分别为多少条？少条？(2) D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有多少条回路？实例实例 0101100101020001A46 100401041005000101031003010400011002010210030001432AAA(1) D中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路条是回路. D中长度为中长度为2的通路为

41、的通路为11条，其中有条，其中有3条是回路条是回路. D中长度为中长度为3的通路为的通路为14条，其中有条，其中有1条是回路条是回路. D中长度为中长度为4的通路为的通路为17条，其中有条，其中有3条是回路条是回路. (2) D中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解47 否否则则可可达达, 1, 0jiijvvp定义定义9.24 设设D=为有向图为有向图. V=v1, v2, , vn, 令令 有向图的可达矩阵有向图的可达矩阵称称 (pij)n n 为为D的的可达矩阵可达矩阵，记作，记作P(D)，简记为，简记为P. P(D)的

42、主对角线上的元素全为的主对角线上的元素全为1. D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵. 1101110111110001P例例48第九章第九章 习题课习题课主要内容主要内容l 无向图和有向图及其有关的概念无向图和有向图及其有关的概念; 握手定理及其推论；图握手定理及其推论；图的同构的同构l 通路与回路通路与回路l 无向图的连通性与连通度无向图的连通性与连通度l 有向图的连通性及其分类有向图的连通性及其分类l 图的矩阵表示图的矩阵表示49基本要求基本要求l 深刻理解图及其有关的概念深刻理解图及其有关的概念l 深刻理解和灵活地应用握手定理及推论深刻理解和灵活地应用握手定理及

43、推论l 记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法l 深刻理解与无向图连通性、连通度有关的诸多概念深刻理解与无向图连通性、连通度有关的诸多概念l 会判别有向图连通性的类型会判别有向图连通性的类型l 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵法，会求可达矩阵 5019阶无向图阶无向图G中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6. 证明证明G中至少有中至少有5个个6度顶点或至少有度顶点或至少有6个个5度顶点度顶点. 练习练习1证证 关键是利用握手定理的推论关键是利用握手定理的推论. 方

44、法一：穷举法方法一：穷举法设设G中有中有x个个5度顶点，度顶点，(9 x)个个6度顶点，由于奇度顶点的度顶点，由于奇度顶点的个数是偶数，个数是偶数，(x, 9 x)只有只有5种可能：种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求）它们都满足要求. 方法二：反证法方法二：反证法否则，至多有否则，至多有4个个5度顶点并且至多有度顶点并且至多有4个个6度顶点，这与度顶点，这与G是是 9 阶图矛盾阶图矛盾. 512存在以存在以2, 2, 2, 2, 3, 3为顶点度数的简单图吗？若存在，画为顶点度数的简单图吗？若存在，画出尽可能多的这种非同构的图来出尽可能多的

45、这种非同构的图来. 练习练习2解解52证证 用扩大路径法证明用扩大路径法证明.设设 +, 证明证明D中存在长度中存在长度 +1的圈的圈. 设设 = v0v1vl为极大路径为极大路径, 则则l . 在在 上存在上存在d (v0) 个顶个顶点点 邻接到邻接到v0, 设设vk是其中离是其中离v0最远的顶点最远的顶点, k . 于是于是, v0v1vkv0为为D中长度中长度 +1的圈的圈 . 当当 + 时时, 类似可证类似可证. 3设设D=为有向简单图为有向简单图, 已知已知 (D) 2, +(D)0, (D)0, 证明证明D中存在长度中存在长度 max +, +1的圈的圈.练习练习353(1) D中

46、有几种不同构的圈？中有几种不同构的圈？(2) D中有几种不同构的非圈简单回路？中有几种不同构的非圈简单回路？(3) D是哪类连通图是哪类连通图?(4) D中中v1到到v4长度为长度为1,2,3,4的通路各多少条？的通路各多少条？(5) D中中v1到到v1长度为长度为1,2,3,4的回路各多少条？的回路各多少条？(6) D中长度为中长度为4的通路（不含回路）有多少条？的通路（不含回路）有多少条？(7) D中长度为中长度为4的回路有多少条？的回路有多少条？(8) D中长度中长度 4的通路有多少条？其中有几条是回路？的通路有多少条？其中有几条是回路？(9) 写出写出D的可达矩阵的可达矩阵. 4有向图

47、有向图D如图所示，如图所示，回答下列诸问：回答下列诸问：练习练习454解答解答解解 (1) 有有3种非同构的圈，长度分别为种非同构的圈，长度分别为1,2,3. 1222234412222465012112220121222310010121100102210100100101000021432AAAA(2) 有有3种非同构的种非同构的非圈非圈简单回路，它们的长度分别为简单回路，它们的长度分别为 4,5,6. (3) D是强连通的是强连通的.为解为解(4)(8), 先求先求D的邻接矩阵的前的邻接矩阵的前4次幂次幂.55(4) v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2. (定义意义下定义意义下). 解答解答(5) v1到到v1长度为长度为1,2,3,4的回路数分别为的回路数分别为1,1,3,5. (6) 长度为长度为4的通路的通路(不含回路不含回路)为为33条条.(7) 长度为长度为4的回路为的回路为11条条. (8) 长度长度 4的通路的通路88条，其中条，其中22条为回路条为回路. (9) 4 4的全的全1矩阵矩阵.