离散数学屈婉玲第九章.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)E为为V

2、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 的多重有穷集的多重有穷集,称为称为边集边集,其元素称为其元素称为有向边有向边,简简称称边边例例 有向图有向图D=,其中其中V=a,b,c,dE=,注意：图的集合

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

4、简单图多重图与简单图定义定义9.3 无向图中关联同一对顶点的无向图中关联同一对顶点的2条和条和2条以上的边称为条以上的边称为平行边平行边.有向图中有向图中2条和条和2条以上始点、终点相同的边称为条以上始点、终点相同的边称为平平行边行边.平行边的条数称为平行边的条数称为重数重数.含平行边的图称为含平行边的图称为多重图多重图,不含平行边和环的图称为不含平行边和环的图称为简单图简单图.定义定义9.4 设设G=为无向图为无向图,v V,称称v作为边的端点的次作为边的端点的次数之和为数之和为v的的度数度数,简称简称度度,记作记作d(v).设设D=为有向图为有向图,v V,称称v作为边的始点的次数之和作为

5、边的始点的次数之和为为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)|v V D的的最小度最小度 (D)=mind(v)|v V D的的最大出度最大出度+(D)=maxd+(v)|v V D的的最小出度最小出度 +(D)=mind+(v)|v

6、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.=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(

7、d)=3,+=4,+=0,=3,=1,=5,=3.9定理定理9.1 在任何无向在任何无向图图中中,所有所有顶顶点的度数之和等于点的度数之和等于边边数的数的2倍倍.证证 G中每条中每条边边(包括包括环环)均有两个端点，所以在均有两个端点，所以在计计算算G中各中各顶顶点度数之和点度数之和时时，每条，每条边边均提供均提供2度，度，m 条条边边共提供共提供 2m 度度.握手定理握手定理定理定理9.2 在任何有向在任何有向图图中，所有中，所有顶顶点的度数之和等于点的度数之和等于边边数的数的2倍倍;所有所有顶顶点的入度之和等于所有点的入度之和等于所有顶顶点的出度之和点的出度之和,都等于都等于边边数数.推论

8、推论 任何图任何图(无向或有向无向或有向)中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数.证证 由握手定理由握手定理,所有顶点的度数之和是偶数所有顶点的度数之和是偶数,而偶度顶点的度而偶度顶点的度数之和是偶数数之和是偶数,故奇度顶点的度数之和也是偶数故奇度顶点的度数之和也是偶数.所以奇度顶所以奇度顶点的个数必是偶数点的个数必是偶数10例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余度顶点，其余均为均为2度顶点度，问度顶点度，问G的阶数的阶数n为几？为几？解解 本题的关键是应用握手定理本题的关键是应用握手定理.设除设除3度与度与4度顶点外，还有度顶点外，还

9、有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=为两个无向图为两个无向图(两个有向两个有向图图)，若存在双射函数，若存在双射函数f:V1V2,使得使得 vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 （E1 当且仅当当且仅当 E2)并且并且,(vi,vj)（）与）与(f(vi),f(vj)（）的重数相）的重数相同，则称同，则称G1与

10、与G2是是同构同构的，记作的，记作G1 G2.例例 12图同构的实例图同构的实例 (1)(2)(3)(4)(1)与与(2),(3)与与(4),(5)与与(6)均不同构均不同构.(5)(6)说明说明:1.图图的同构关系具有自反性、的同构关系具有自反性、对对称性和称性和传递传递性性.2.判断两个判断两个图图同构是个同构是个难题难题图同构的实例图同构的实例所有所有4阶阶3条条边边非同构的非同构的简单简单无向无向图图13所有所有3阶阶2条条边边非同构的非同构的简单简单有向有向图图补图补图与自补图与自补图定定义义9.6 设设G=为为n阶阶无向无向简单图简单图，令，令 =(u,v)|u V v V u v

11、(u,v)E,称称 =为为G的的补图补图 若若G 则则称称G是是自自补图补图 例例 (b)与与(c)互互为补图为补图，(a)是自是自补图补图15完全图与竞赛图完全图与竞赛图定义定义9.7 (1)n(n 1)阶阶无向完全图无向完全图每个顶点与其余顶点均相邻的每个顶点与其余顶点均相邻的无向简单图，记作无向简单图，记作 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)阶阶

12、竞赛图竞赛图基图为基图为Kn的有向简单图的有向简单图.简单性质：简单性质：m=n(n-1)/2,=n-1 正则图正则图 K5 3阶有向完全图阶有向完全图 4阶竞赛图阶竞赛图定义定义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

13、 E，则则称称G 为为G的的真子真子图图.若若G G且且V=V，则则称称G 为为G的的生成子生成子图图 设设V1 V且且V1,称以称以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，称，称为为删

14、删除除边边e又又设设E E，用，用 G E 表示从表示从G中中删删除除E 中的所有中的所有边边，称，称为为删删除除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关关联联的所有的所有边边，称，称

15、为为收收缩边缩边e (4)设设u,v V（u,v可能相可能相邻邻，也可能不相，也可能不相邻邻），用），用G(u,v)（或（或G+(u,v)）表示在）表示在u,v之之间间加一条加一条边边(u,v)，称，称为为加加新新边边 在收在收缩边缩边和加新和加新边过边过程中可能程中可能产产生生环环和平行和平行边边 删除删除,收缩与加新边收缩与加新边19实例实例v1v2v3v4v5e1e2e3e4e5e6e7Gv1v2v3v4v5e1e2e3e4e6e7G-e5v1v2v3v4v5e2e3e5e6e7G-e1,e4v1v2v3v4e3e4e5e6e7G-v5v1v2v3e4e5e7G-v4,v5v1v3v4v

16、5e1e2e3e4e6e7Ge5209.2 通路与回路通路与回路定义定义9.11 设图设图G=(无向或有向的无向或有向的),G中顶点与边的交中顶点与边的交替序列替序列 =v0e1v1e2elvl，如果，如果vi 1,vi 是是 ei 的端点的端点(始点和终始点和终点点),1 i l,则称则称 为为v0到到vl的的通路通路.v0,vl分别称作分别称作 的的始点始点和和终终点点.中的边数中的边数l称作它的称作它的长度长度.又又若若 v0=vl,则称则称 为为回路回路.若若所有的边各异所有的边各异,则称则称 为为简单通路简单通路.又若又若v0=vl,则称则称 为为简单回简单回路路.若若 中所有顶点各

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

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

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

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

21、的图图称称为为带权图带权图,记记作作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).约

22、约定定: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关关联联的的临时标临时标号的号的顶顶点点v 3.if l

23、2(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总部总部12345671510364451726 (0,S)(+,S)(+,S)(+,S

24、)(+,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)(18,5)(14,3)(30,2)(16,5)u=528实例实例12345671510364

25、451726 (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)=2212345671510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5

26、)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关于关于顶顶点之点之间连间连通关通关系的一个等价系的一个等价类类，称，称导导出子出子图图GVi为为G的一个的一个连连

27、通分支通分支.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),则则称称E 是是G的的边边割集割集，简简称称为为割集割集.若若E =e,则则称称e为为割割边边或或桥桥例例3 v1,v4，v6是点割集，是点割集，v

28、6是割点是割点.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,非连通图的连通度为非连通图的连通度为0.定义定义9.18 设设G为连通图为连通图,称称 (G)=min|E|E 为边割集为边割集为为G的的边连通度边连通度.若若(G)r，则称，则称G

29、是是 r 边边-连通图连通图.规定非连通图的边连通度为规定非连通图的边连通度为0.v1v2v3v4v5e1e2e3e4e5e6e7例例 =2,2-连通图连通图,也是也是1-连通连通.=2,2边边-连通图连通图,也是也是1边边-连通连通.33几点说明几点说明l(Kn)=(Kn)=n 1lG非连通，则非连通，则 =0l若若G中有割点，则中有割点，则=1，若有桥，则，若有桥，则=1l若若(G)=k,则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1l若若(G)=r,则则G是是1边边-连通图，连通图，2边边-连通图，连通图，r边边-连通

30、连通图，但不是图，但不是(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，则则称称vi与与vj是是相互可达相互可达的的,记记作作vivj.规规定定vivi性质性质:具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 定定义义9.20 若有向若有向图图D=V,E)的基的基图图是是连连通

31、通图图,则则称称D是是弱弱连连通通图图,简简称称为为连连通通图图.若若 vi,vj V,vivj与与vjvi至少有一个成立，至少有一个成立，则则称称 D是是单单向向连连通通图图.若若 vi,vj V,均有均有vivj,则则称称D是是强强连连通通图图35有向图的连通性有向图的连通性 强连通强连通 单向连通单向连通 弱连通弱连通定理定理9.7 有向有向图图D=是是强强连连通通图图当且当且仅仅当当D中存在中存在经过经过每个每个顶顶点至少一次的回路点至少一次的回路证证 充分性充分性显显然然.证证必要性必要性.设设V=v1,v2,vn,i为为vi到到vi+1的通的通路路(i=1,2,n 1),n为为vn

32、到到v1的通路的通路.依次依次连连接接 1,2,n 1,n所得到的回路所得到的回路经过经过D中每个中每个顶顶点至少一次点至少一次定理定理9.8 有向有向图图D是是单单向向连连通通图图当且当且仅仅当当D中存在中存在经过经过每个每个顶顶点至少一次的通路点至少一次的通路例例扩大路径法扩大路径法设设G=为无向图为无向图,为为G中一条路径中一条路径.若此路径的两个端若此路径的两个端点都不与通路外的顶点相邻点都不与通路外的顶点相邻,则称则称 是是极大路径极大路径.任取一条边任取一条边,如果它有一个端点与其他的顶点相邻如果它有一个端点与其他的顶点相邻,就将这条就将这条边延伸到这个顶点边延伸到这个顶点.继续这

33、一过程继续这一过程,直至得到一条极大路径为直至得到一条极大路径为止止.称此种方法为称此种方法为“扩大路径法扩大路径法”.用扩大路径法总可以得到用扩大路径法总可以得到一条极大路径一条极大路径.在有向图中可类似讨论在有向图中可类似讨论.例例 由一条路径扩大出的极大路径不惟一，极大路径不一定是由一条路径扩大出的极大路径不惟一，极大路径不一定是最长的路径最长的路径37扩大路径法的应用扩大路径法的应用例例4 设设 G 为为 n（n 3）阶无向简单图，）阶无向简单图，2，证明，证明G 中存在中存在长度长度 +1 的圈的圈.证证 设设 =v0v1vl 是一条极大路径是一条极大路径,则则 l .因为因为v0

34、不与不与 外外顶点相邻顶点相邻,又又 d(v0),因而在因而在 上除上除 v1外外,至少还存在至少还存在 1个个顶点与顶点与 v0 相邻相邻.设设 vx 是离是离 v0 最远的顶点最远的顶点,于是于是v0v1vxv0 为为 G 中长度中长度 +1 的圈的圈.389.4 图的矩阵表示图的矩阵表示无向图的关联矩阵无向图的关联矩阵定义定义9.21 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G).例例39无向图关联矩阵的性质无向图关联矩阵的性质40定义定义9.22 设有向图有向图

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

36、的的邻接矩阵邻接矩阵，记作，记作A(D)，或简记为，或简记为A.例例43有向图邻接矩阵的性质有向图邻接矩阵的性质定理定理9.9 设设 A为为有向有向图图 D 的的邻邻接矩接矩阵阵,顶顶点集点集V=v1,v2,vn，则则 A 的的 l 次次幂幂 Al（l 1）中元素）中元素推推论论 设设Bl=A+A2+Al(l 1),则则为长为长度小于或等于度小于或等于 l 的回路数的回路数.为长为长度小于或等于度小于或等于 l 的通路数的通路数,邻接矩阵的应用邻接矩阵的应用为长度为 l 的通路总数，为vi 到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为长度为为长度为 l 的回路总数的回路总数

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

38、长度度为为4的通路的通路为为17条，其中有条，其中有3条是回路条是回路.(2)D中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解47定定义义9.24 设设D=为为有向有向图图.V=v1,v2,vn,令令 有向图的可达矩阵有向图的可达矩阵称称(pij)n n 为为D的的可达矩阵可达矩阵，记作，记作P(D)，简记为，简记为P.P(D)的主对角线上的元素全为的主对角线上的元素全为1.D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵.例例48第九章第九章 习题课习题课主要内容主要内容l无向图和有向图及其有关的概念无向图和有向图及其有

39、关的概念;握手定理及其推论；图握手定理及其推论；图的同构的同构l通路与回路通路与回路l无向图的连通性与连通度无向图的连通性与连通度l有向图的连通性及其分类有向图的连通性及其分类l图的矩阵表示图的矩阵表示49基本要求基本要求l深刻理解图及其有关的概念深刻理解图及其有关的概念l深刻理解和灵活地应用握手定理及推论深刻理解和灵活地应用握手定理及推论l记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法l深刻理解与无向图连通性、连通度有关的诸多概念深刻理解与无向图连通性、连通度有关的诸多概念l会判别有向图连通性的类型会判别有向图连通性的类型l熟练掌握用邻接矩阵及其幂求有向图中通路与回路数

40、的方熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵法，会求可达矩阵 5019阶无向图阶无向图G中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6.证明证明G中至少有中至少有5个个6度顶点或至少有度顶点或至少有6个个5度顶点度顶点.练习练习1证证 关键是利用握手定理的推论关键是利用握手定理的推论.方法一：穷举法方法一：穷举法设设G中有中有x个个5度顶点，度顶点，(9 x)个个6度顶点，由于奇度顶点的度顶点，由于奇度顶点的个数是偶数，个数是偶数，(x,9 x)只有只有5种可能：种可能：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求）它们都满足要求

41、.方法二：反证法方法二：反证法否则，至多有否则，至多有4个个5度顶点并且至多有度顶点并且至多有4个个6度顶点，这与度顶点，这与G是是 9 阶图矛盾阶图矛盾.512存在以存在以2,2,2,2,3,3为顶点度数的简单图吗？若存在，画为顶点度数的简单图吗？若存在，画出尽可能多的这种非同构的图来出尽可能多的这种非同构的图来.练习练习2解解52证证 用扩大路径法证明用扩大路径法证明.设设 +,证明证明D中存在长度中存在长度 +1的圈的圈.设设 =v0v1vl为极大路径为极大路径,则则l .在在 上存在上存在d(v0)个个顶点顶点 邻接到邻接到v0,设设vk是其中离是其中离v0最远的顶点最远的顶点,k .

42、于是于是,v0v1vkv0为为D中长度中长度 +1的圈的圈.当当 +时时,类似可证类似可证.3设设D=为有向简单图为有向简单图,已知已知 (D)2,+(D)0,(D)0,证明证明D中存在长度中存在长度 max +,+1的圈的圈.练习练习353(1)D中有几种不同构的圈？中有几种不同构的圈？(2)D中有几种不同构的非圈简单回路？中有几种不同构的非圈简单回路？(3)D是哪类连通图是哪类连通图?(4)D中中v1到到v4长度为长度为1,2,3,4的通路各多少条？的通路各多少条？(5)D中中v1到到v1长度为长度为1,2,3,4的回路各多少条？的回路各多少条？(6)D中长度为中长度为4的通路（不含回路）

43、有多少条？的通路（不含回路）有多少条？(7)D中长度为中长度为4的回路有多少条？的回路有多少条？(8)D中长度中长度 4的通路有多少条？其中有几条是回路？的通路有多少条？其中有几条是回路？(9)写出写出D的可达矩阵的可达矩阵.4有向图有向图D如图所示，如图所示，回答下列诸问：回答下列诸问：练习练习454解答解答解解 (1)有有3种非同构的圈，长度分别为种非同构的圈，长度分别为1,2,3.(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矩阵矩阵.