图论基本概念PPT课件

1、1第五部分第五部分 图论图论本部分主要内容本部分主要内容l 图的基本概念图的基本概念l 欧拉图、哈密顿图欧拉图、哈密顿图l 树树2绪论绪论图论的历史：图论的历史： 图论的第一篇论文是瑞士数学家欧拉（图论的第一篇论文是瑞士数学家欧拉（euler）发表于）发表于1736年出版的年出版的圣彼得堡科学院刊物中。圣彼得堡科学院刊物中。讨论一个所谓讨论一个所谓konigsberg seven bridges problem。3绪论绪论图论的作用：图论的作用：l 图与计算机：计算机中数据结构，离不开数组、串、各种图与计算机：计算机中数据结构，离不开数组、串、各种链接表、树和图，因此图是计算机中数据表示、存储

2、和运链接表、树和图，因此图是计算机中数据表示、存储和运算的基础算的基础 l 图与网络：图与网络： 最大流问题：假设从城市最大流问题：假设从城市p到城市到城市q的一个公路网，的一个公路网， 公路网中每段公路上每天可以通过的汽车的数量有上限，公路网中每段公路上每天可以通过的汽车的数量有上限，那么经过该公路网，每天最多可以有多少辆汽车从城市那么经过该公路网，每天最多可以有多少辆汽车从城市p开到城市开到城市q？ 最优支撑树问题：某一地区有若干个主要城市，拟最优支撑树问题：某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得从其中任何一个修建高速公路把这些城市连接起来，使得从其中任何一个城市

3、都可以经高速公路直接或间接到达另一个城市。假设城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本，那么已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？应如何决定在哪些城市间修建高速公路，使得总成本最小？4第十四章第十四章 图的基本概念图的基本概念主要内容主要内容l 图图l 通路与回路通路与回路l 图的连通性图的连通性l 图的矩阵表示图的矩阵表示l 图的运算图的运算预备知识预备知识l 多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合l 无序集无序集a b=(x,y) | x a y b5

4、14.1 图图定义定义14.1 无向图无向图g = , 其中其中(1) v 为顶点集，元素称为为顶点集，元素称为顶点顶点 vertex(2) e为为v v 的多重集，其元素称为无向边，简称的多重集，其元素称为无向边，简称边边 edge实例实例 设设 v = v1, v2, ,v5, e = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则则 g = 为一无向图为一无向图6有向图有向图定义定义14.2 有向图有向图d=, 只需注意只需注意e是是v v 的多重子集的多重子集图图2表示的是一个有向图，试写出它的表示的是一个

5、有向图，试写出它的v 和和 e 注意：图的数学定义与图形表示，在同构（待叙）的意义下注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的是一一对应的7相关概念相关概念1. 图图 可用可用g泛指图（无向的或有向的）泛指图（无向的或有向的） v(g), e(g), |v(g)|, |e(g)| n阶图：阶图：n 个顶点的图个顶点的图2. 有限图有限图3. n 阶零图（阶零图（0条边）与平凡图（条边）与平凡图（1个顶点）个顶点）4. 空图空图（运算中出现）（运算中出现）5. 用用 ek 表示无向边或有向边表示无向边或有向边8相关概念相关概念6. 顶点与边的关联关系顶点与边的关联关系 关联

6、、关联次数关联、关联次数 环环 孤立点孤立点7. 顶点之间的相邻与邻接关系顶点之间的相邻与邻接关系9)()()(),()(|)(vvnvnvvugevugvuuvnv 的的闭闭邻邻域域的的邻邻域域)(|)(关关联联与与vegeeevi )()()()()()(,)(|)()(,)(|)(vvnvnvvvvnvvudevudvuuvvvudeuvdvuuvvddddddd 的的闭闭邻邻域域的的邻邻域域的的先先驱驱元元集集的的后后继继元元集集8. 邻域与关联集邻域与关联集 v v(g) (g为无向图为无向图) v 的关联集的关联集 v v(d) (d为有向图为有向图)9. 标定图与非标定图标定图与

7、非标定图(顶点和边指定编号的）顶点和边指定编号的）10. 基图（有向图的有向边改为无向边）基图（有向图的有向边改为无向边）相关概念相关概念10多重图与简单图多重图与简单图定义定义14.3 (1) 无向图中的平行边及重数无向图中的平行边及重数 关联一对顶点的边多于一条，条数称为重数关联一对顶点的边多于一条，条数称为重数 (2) 有向图中的平行边及重数（注意方向性）有向图中的平行边及重数（注意方向性） (3) 多重图多重图 (4) 简单图（无平行边和环）简单图（无平行边和环）简单图是极其重要的概念简单图是极其重要的概念 11顶点的度数顶点的度数定义定义14.4 (1) 设设g=为无向图为无向图,

8、v v, d(v)v的度数的度数, 简称度简称度 (2) 设设d=为有向图为有向图, v v, d+(v)v的出度的出度 d (v)v的入度的入度 d(v)v的度或度数的度或度数 (3) (g)（最大度）（最大度）, (g)（最小度）（最小度） 无向图中无向图中 (4) +(d), +(d), (d), (d), (d), (d) (5) 度数为度数为1的点称为悬挂点，关联的边为悬挂边；的点称为悬挂点，关联的边为悬挂边； 奇顶点度与偶度顶点奇顶点度与偶度顶点12mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 设设g=为任意无向图，为任意无向

9、图，v=v1,v2,vn, |e|=m, 则则证证 g中每条边中每条边 (包括环包括环) 均有两个端点，所以在计算均有两个端点，所以在计算g中各顶点中各顶点度数之和时，每条边均提供度数之和时，每条边均提供2度，度，m 条边共提供条边共提供 2m 度度.此二定理是欧拉此二定理是欧拉17361736年给出，是图论的基本定理年给出，是图论的基本定理握手定理握手定理定理定理14.2 设设d=为任意有向图，为任意有向图，v=v1,v2,vn, |e|=m, 则则13握手定理推论握手定理推论推论推论 任何图任何图 (无向或有向无向或有向) 中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数.证证 设设g=为

10、任意图，令为任意图，令 v1=v | v v d(v)为奇数为奇数 v2=v | v v d(v)为偶数为偶数 则则v1 v2=v, v1 v2=，由握手定理可知，由握手定理可知由于由于2m, 均为偶数，所以均为偶数，所以 为偶数，但因为为偶数，但因为v1中中顶点度数为奇数，所以顶点度数为奇数，所以|v1|必为偶数必为偶数. 21)()()(2vvvvvvvdvdvdm 2)(vvvd 1)(vvvd14图的度数列图的度数列1 . v=v1, v2, , vn为无向图为无向图g的顶点集，称的顶点集，称d(v1), d(v2), , d(vn)为为g的的度数列度数列 2. v=v1, v2, ,

11、 vn为有向图为有向图d的顶点集，的顶点集， d的的度数列度数列：d(v1), d(v2), , d(vn) d的的出度列出度列：d+(v1), d+(v2), , d+(vn) d的的入度列入度列：d (v1), d (v2), , d (vn) 3. 非负整数列非负整数列d=(d1, d2, , dn)是是可图化的可图化的，是，是可简单图化可简单图化的的.易知：易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可是可图化的，后者又是可简单图化的，而简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简单图化都不是可简单图

12、化的，特别是后者也不是可图化的的，特别是后者也不是可图化的15图的同构图的同构定义定义14.5 设设g1=, g2=为两个无向图为两个无向图(两个有向两个有向图图)，若存在双射函数，若存在双射函数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. l 图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.l 能找

13、到多条同构的必要条件，但它们全不是充分条件：能找到多条同构的必要条件，但它们全不是充分条件： 边数相同，顶点数相同边数相同，顶点数相同; 度数列相同度数列相同; 对应顶点的关联集及邻域的元素个数相同，等等对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构l 判断两个图同构是个难题判断两个图同构是个难题16图同构的实例图同构的实例图中图中(1)与与(2)的度数列相同，它们同构吗？为什么？的度数列相同，它们同构吗？为什么？ (1) (2) (3) (4) 图中，图中，(1)与与(2)不同构（度数列不同），不同构（度数列不同），(3)与与(4)也不同

14、构也不同构. (1) (2) 17n 阶完全图与竞赛图阶完全图与竞赛图定义定义14.6 (1) n (n 1) 阶无向完全图阶无向完全图每个顶点与其余顶点均相邻的每个顶点与其余顶点均相邻的无向简单图，记作无向简单图，记作 kn.简单性质：边数简单性质：边数(2) n (n 1)阶阶有向完全图有向完全图每对顶点之间均有两条方向相每对顶点之间均有两条方向相反的有向边的有向简单图反的有向边的有向简单图.简单性质：简单性质： (3) n (n 1) 阶阶竞赛图竞赛图基图为基图为kn的有向简单图的有向简单图.简单性质：边数简单性质：边数1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1

15、( nnnm 18n 阶阶 k 正则图正则图(1)为为k5，(2)为为3阶有向完全图，阶有向完全图，(3)为为4阶竞赛图阶竞赛图. (1) (2) (3)定义定义14.7 n 阶阶k正则图正则图 = =k 的无向简单图的无向简单图简单性质：边数（由握手定理得）简单性质：边数（由握手定理得）kn是是 n 1正则图，正则图，彼得松图（见书上图彼得松图（见书上图14.3(1) 所示，记住它）所示，记住它）2nkm 19子图子图定义定义14.8 g=, g =(1) gg g 为为g的的子图子图，g为为g 的的母图母图(2) 若若gg且且v =v，则称，则称g 为为g的的生成子图生成子图(3) 若若v

16、v或或ee，称，称g 为为g的的真子图真子图(4) v （vv且且v）的）的导出子图导出子图，记作，记作gv (5) e （ee且且e）的）的导出子图导出子图，记作，记作ge 20例例2 画出画出k4的所有非同构的生成子图的所有非同构的生成子图实例实例21补图补图定义定义14.9 设设g=为为n阶无向简单图，以阶无向简单图，以v为顶点集，以为顶点集，以所有使所有使g成为完全图成为完全图kn的添加边组成的集合为边集的图，的添加边组成的集合为边集的图，称为称为g的的补图补图，记作，记作 .若若g , 则称则称g是是自补图自补图. 相对于相对于k4, 求上面图中所有图的补图，并指出哪些是自补图求上面

17、图中所有图的补图，并指出哪些是自补图. 问：互为自补图的两个图的边数有何关系？问：互为自补图的两个图的边数有何关系？gg2214.2 通路与回路通路与回路定义定义14.11 给定图给定图g=（无向或有向的），（无向或有向的），g中中顶点与顶点与边的交替序列边的交替序列 = v0e1v1e2elvl，vi 1, vi 是是 ei 的端点的端点.(1) 通路与回路：通路与回路： 为为通路通路；若；若 v0=vl， 为为回路回路，l 为为回路长回路长 度度.(2) 简单通路与回路：所有边各异，简单通路与回路：所有边各异， 为为简单通路简单通路，又若，又若v0=vl， 为为简单回路简单回路(3) 初级

18、通路初级通路(路径路径)与初级回路与初级回路(圈圈)： 中所有顶点各异，则中所有顶点各异，则称称 为为初级通路初级通路(路径路径)，又若除，又若除v0=vl，所有的顶点各不相，所有的顶点各不相同且所有的边各异，则称同且所有的边各异，则称 为为初级回路初级回路(圈圈)(4) 复杂通路与回路：有边重复出现复杂通路与回路：有边重复出现23几点说明几点说明表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法（在简单图中）只用顶点表示法（在简单图中） 混合表示法混合表示法环环（长为（长为1的圈）的长度为的圈）的长度为1，两条平行边构成的圈长度为，两条平行边构成的圈长度为 2，无向

19、简单图中，圈长，无向简单图中，圈长 3，有向简单图中圈的长度，有向简单图中圈的长度 2. 不同的圈（以长度不同的圈（以长度 3的为例）的为例） 定义意义下定义意义下 无向图：图中长度为无向图：图中长度为l（l 3）的圈，定义意义下为）的圈，定义意义下为2l个个 有向图：图中长度为有向图：图中长度为l（l 3）的圈，定义意义下为）的圈，定义意义下为l个个 同构意义下：长度相同的圈均为同构意义下：长度相同的圈均为1个个试讨论试讨论l=3和和l=4的情况的情况24通路与回路的长度通路与回路的长度定理定理14.5 在在n 阶图阶图g中，若从顶点中，若从顶点vi 到到vj（vi vj）存在通路，）存在通

20、路，则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 的通路的通路.推论推论 在在 n 阶图阶图g中，若从顶点中，若从顶点vi 到到 vj（vi vj）存在通路，则）存在通路，则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1的初级通路（路径）的初级通路（路径）.定理定理14.6 在一个在一个n 阶图阶图g中，若存在中，若存在 vi 到自身的回路，则一到自身的回路，则一定存在定存在vi 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在一个在一个n 阶图阶图g中，若存在中，若存在 vi 到自身的简单回路，则一到自身的简单回路，则一定存在长

21、度小于或等于定存在长度小于或等于n 的初级回路的初级回路.2514.3 图的连通性图的连通性无向图的连通性无向图的连通性(1) 顶点之间的连通关系：顶点之间的连通关系：g=为无向图为无向图 若若 vi 与与 vj 之间有通路，则之间有通路，则 vi vj 是是v上的等价关系上的等价关系 r=| u,v v且且u v (2) g的连通性与连通分支的连通性与连通分支 若若 u,v v，u v，则称，则称g连通连通 v/r=v1,v2,vk，称，称gv1, gv2, ,gvk为为连通分连通分 支支，其个数，其个数 p(g)=k (k 1)； k=1，g连通连通26短程线与距离短程线与距离(3) 短程

22、线与距离短程线与距离 u与与v之间的之间的短程线短程线：u v，u与与v之间长度最短的通路之间长度最短的通路 u与与v之间的之间的距离距离：d(u,v)短程线的长度短程线的长度 d(u,v)的性质：的性质： d(u,v) 0, u v时时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w)27无向图的连通度无向图的连通度1. 删除顶点及删除边删除顶点及删除边 g v 从从g中将中将v及关联的边去掉及关联的边去掉 g v 从从g中删除中删除v 中所有的顶点中所有的顶点 g e 将将e从从g中去掉中去掉 g e 删除删除e 中所有边中所有边 2. 点割集与边割集点割

23、集与边割集 点割集与割点点割集与割点定义定义14.16 g=, vv v 为为点割集点割集p(g v )p(g)且有极小性且有极小性 v为为割点割点v为点割集为点割集定义定义14.17 g=, ee e 是是边割集边割集p(g e )p(g)且有极小性且有极小性 e是是割边割边（桥）（桥）e为边割集为边割集28点割集与割点点割集与割点例例3 v1,v4，v6是点是点割集，割集，v6是割点是割点. v2,v5是点割集吗？是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，等是边割集，e8是是桥，桥，e7,e9,e5,e6 是边割是边割集吗？集吗？几点说明：几点说明：l kn中无点割集

24、，中无点割集，nn中既无点割集，也无边割集，其中中既无点割集，也无边割集，其中nn为为 n 阶零图阶零图. l 若若g 连通，连通，e 为边割集，则为边割集，则 p(g e )=2，v 为点割集，则为点割集，则 p(g v ) 2 29点连通度与边连通度点连通度与边连通度定义定义14.18 g为连通非完全图为连通非完全图 点连通度点连通度 (g) = min |v | v 为点割集为点割集 规定规定 (kn) = n 1 若若g非连通，非连通， (g) = 0 若若 (g) k，则称，则称g为为 k-连通图连通图 定义定义14.19 设设g为连通图为连通图 边连通度边连通度 (g) = min

25、|e | e 为边割集为边割集 若若g非连通，则非连通，则 (g) = 0 若若 (g) r，则称，则称g是是 r 边边-连通图连通图图中，图中， = =1，它是，它是 1-连通图连通图 和和 1边边-连通图连通图30几点说明几点说明l (kn)= (kn)=n 1l g非连通，则非连通，则 = =0l 若若g中有割点，则中有割点，则 =1，若有桥，则，若有桥，则 =1l 若若 (g)=k, 则则g是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1l 若若 (g)=r, 则则g是是1-边连通图，边连通图，2-边连通图，边连通图，r-边

26、连通边连通图，但不是图，但不是(r+s)-边连通图，边连通图，s 1l , , 之间的关系之间的关系.定理定理7.5 (g)(g)(g)请画出一个请画出一个 的无向简单图的无向简单图31有向图的连通性有向图的连通性定义定义14.20 d=为有向图为有向图 vi vj（vi 可达可达 vj）vi 到到vj 有通路有通路 vi vj（vi 与与vj 相互可达）相互可达）性质性质 具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 vi 到到vj 的短程线与距离的短程线与距离类似于无向图中，只需注意距离表示法的不同类似于无向图中，只需注意距离表示

27、法的不同(无向图中无向图中d(vi,vj)，有向图中，有向图中d) 及及 d无对称性无对称性32有向图的连通性及分类有向图的连通性及分类定义定义14.22 d=为有向图为有向图 d弱连通弱连通(连通连通)基图为无向连通图基图为无向连通图 d单向连通单向连通 vi,vj v，vivj 或或 vjvi d强连通强连通 vi,vj v，vivj易知，强连通易知，强连通单向连通单向连通弱连通弱连通判别法判别法定理定理14.8 d强连通当且仅当强连通当且仅当d中存在经过每个顶点至少一次中存在经过每个顶点至少一次的回路的回路定理定理14.9 d单向连通当且仅当单向连通当且仅当d中存在经过每个顶点至少一中存

28、在经过每个顶点至少一次的通路次的通路33扩大路径法扩大路径法无向图中无向图中设设g=为为 n 阶无向图，阶无向图，e. 设设 l 为为g中一条路径，若中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止与通路外的顶点相邻为止. 设最后得到的路径为设最后得到的路径为 l+k（长度（长度为为 l 的路径扩大成了长度为的路径扩大成了长度为 l+k 的路径），称的路径），称 l+k为为“极大路极大路径径”，称使用

29、此种方法证明问题的方法为，称使用此种方法证明问题的方法为“扩大路径法扩大路径法”.有向图中类似讨论，只需注意，在每步扩大中保证有向边方有向图中类似讨论，只需注意，在每步扩大中保证有向边方向的一致性向的一致性.34实例实例由某条路径扩大出的极大路径不惟一，极大路径不一定是由某条路径扩大出的极大路径不惟一，极大路径不一定是图中最长的路径图中最长的路径上图中，上图中，(1)中实线边所示的长为中实线边所示的长为2的初始路径的初始路径 ，(2),(3),(4)中实线边所示的都是它扩展成的极大路径中实线边所示的都是它扩展成的极大路径. 还能找到另外的极大路径吗？还能找到另外的极大路径吗？ (1) (2)

30、(4) (3)35扩大路径法的应用扩大路径法的应用例例4 设设 g 为为 n（n 3）阶无向简单图，）阶无向简单图， 2，证明，证明g 中存在中存在长度长度 +1 的圈的圈.证证 设设 = v0v1vl 是由初始路径是由初始路径 0 用扩大路径法的得到的极用扩大路径法的得到的极大路径，则大路径，则 l （为什么？）（为什么？）. 因为因为v0 不与不与 外顶点相邻，又外顶点相邻，又 d(v0) ，因而在，因而在 上除上除 v1外，至少还存在外，至少还存在 1个顶点与个顶点与 v0 相邻相邻. 设设 vx 是离是离 v0 最远的顶最远的顶点，于是点，于是 v0v1vxv0 为为 g 中长度中长度

31、 +1 的圈的圈. 36二部图二部图定义定义14.23 设设 g=为一个无向图，若能将为一个无向图，若能将 v分成分成 v1和和v2(v1 v2=v，v1 v2=)，使得，使得 g 中的每条边的两个端点都是中的每条边的两个端点都是一个属于一个属于v1，另一个属于，另一个属于v2，则称，则称 g 为为二部图二部图 ( 或称或称二分二分图图、偶图偶图等等 )，称，称v1和和v2为为互补顶点子集互补顶点子集，常将二部图，常将二部图g记为记为. 又若又若g是简单二部图，是简单二部图，v1中每个顶点均与中每个顶点均与v2中所有的顶点相中所有的顶点相邻，则称邻，则称g为为完全二部图完全二部图，记为，记为

32、kr,s，其中，其中r=|v1|，s=|v2|. 注意，注意，n 阶零图为二部图阶零图为二部图. 37二部图的判别法二部图的判别法定理定理14.10 无向图无向图g=是是二部图二部图当且仅当当且仅当g中无奇圈中无奇圈 由定理由定理14.10可知图可知图9中各图都是二部图，哪些是完全二部中各图都是二部图，哪些是完全二部图？哪些图是同构的？图？哪些图是同构的？3814.4 图的矩阵表示图的矩阵表示无向图的关联矩阵（对图无限制）无向图的关联矩阵（对图无限制）定义定义14.24 无向图无向图g=，|v|=n，|e|=m，令，令 mij为为 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为

33、为g 的的关联矩阵关联矩阵，记为，记为m(g). 性质性质平行边的列相同平行边的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 39 jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1( 的的终终点点为为，不不关关联联与与，的的始始点点为为jijijiijevevevm10,1有向图的关联矩阵（无环有向图） 定义定义14.25 有向图有向图d=，令，令则称则称 (mij)n m为为d的的关联矩阵关联矩阵，记为，记为

34、m(d). (4) 平行边对应的列相同平行边对应的列相同性质性质有向图的关联矩阵40有向图的邻接矩阵（无限制）有向图的邻接矩阵（无限制）定义定义14.26 设有向图设有向图d=, v=v1, v2, , vn, e=e1, e2, , em, 令为顶点令为顶点 vi 邻接到顶点邻接到顶点 vj 边的条数，称为边的条数，称为d的的邻接矩邻接矩阵阵，记作，记作a(d)，或简记为，或简记为a. 性质性质 的回路数的回路数中长度为中长度为的通路数的通路数中长度为中长度为1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(dadmanjvdanivda

35、niiijiijjniijinjij 41推论推论 设设bl=a+a2+al（l 1），则），则 bl中元素中元素为d中长度为 l 的通路总数，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理定理14.11 设设 a为有向图为有向图 d 的邻接矩阵，的邻接矩阵，v=v1, v2, , vn为为顶点集，则顶点集，则 a 的的 l 次幂次幂 al（l 1）中元素）中元素为d中vi 到vj长度为 l 的通路数，其中为vi到自身长度为 l 的回路数，而为为d中长度小于或等于中长度小于或等于 l 的回路数的回路数为为d中长度小于或等

36、于中长度小于或等于 l 的通路数的通路数. 邻接矩阵的应用邻接矩阵的应用为为d 中长度为中长度为 l 的回路总数的回路总数. 42例例5 有向图有向图d如图所示，求如图所示，求 a, a2, a3, a4，并回答诸问题：，并回答诸问题：(1) d 中长度为中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多的通路各有多少条？其中回路分别为多少条？少条？(2) d 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有多少条回路？实例实例43 100401041005000101031003010400011002010210030001010110

37、0101020001432aaaa(1) d中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路条是回路. d中长度为中长度为2的通路为的通路为11条，其中有条，其中有3条是回路条是回路. d中长度为中长度为3和和4的通路分别为的通路分别为14和和17条，回路分别条，回路分别 为为1与与3条条.(2) d中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解44 否否则则可可达达, 1, 0jiijvvp 1101110111110001p定义定义14.27 设设d=为有向图为有向图. v=v1, v2, , vn, 令令 有向

38、图的可达矩阵（无限制）有向图的可达矩阵（无限制）称称 (pij)n n 为为d的可达矩阵，记作的可达矩阵，记作p(d)，简记为，简记为p. 由于由于 vi v，vivi，所以，所以p(d)主对角线上的元素全为主对角线上的元素全为1. 由定义不难看出由定义不难看出, d 强连通当且仅当强连通当且仅当 p(d)为全为全1矩阵矩阵. 下图所示有向图下图所示有向图 d 的可达矩阵为的可达矩阵为45第十四章第十四章 习题课习题课主要内容主要内容l 无向图、有向图、关联与相邻、简单图、完全图、正则图、无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构子图、补图；握手定

39、理与推论；图的同构l 通路与回路及其分类通路与回路及其分类l 无向图的连通性与连通度无向图的连通性与连通度l 有向图的连通性及其分类有向图的连通性及其分类l 图的矩阵表示图的矩阵表示46基本要求基本要求l 深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解握手定理及推论的内容并能灵活地应用它们l 深刻理解图同构、简单图、完全图、正则图、子图、补图、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系二部图的概念以及它们的性质及相互之间的关系l 记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法l 深刻理解与无向图连通性、连通度有关

40、的诸多概念深刻理解与无向图连通性、连通度有关的诸多概念l 会判别有向图连通性的类型会判别有向图连通性的类型l 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵法，会求可达矩阵 4719阶无向图阶无向图g中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6. 证明证明g中至少有中至少有5个个6度顶点或至少有度顶点或至少有6个个5度顶点度顶点. 练习练习1证证 关键是利用握手定理的推论关键是利用握手定理的推论. 方法一：穷举法方法一：穷举法设设g中有中有x个个5度顶点，则必有度顶点，则必有(9 x)个个6度顶点，由握手定度顶点

41、，由握手定理推论可知，理推论可知，(x,9 x)只有只有5种可能：种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求）它们都满足要求. 方法二：反证法方法二：反证法否则，由握手定理推论可知，否则，由握手定理推论可知，“g至多有至多有4个个5度顶点并且度顶点并且至多有至多有4个个6度顶点度顶点”，这与，这与g是是 9 阶图矛盾阶图矛盾. 482数组数组2, 2, 2, 2, 3, 3能简单图化吗？若能，画出尽可能多的能简单图化吗？若能，画出尽可能多的非同构的图来非同构的图来. 练习练习2只要能画出只要能画出6 阶无向简单图，就说明它可简单图化阶无向简单图，就说明它可简单图化. 下图的下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是个图都以此数列为度数列，请证明它们彼此不同构，都是k6的子图的子图.49用扩大路径法证明用扩大路径法证