离散数学ch公开课一等奖优质课大赛微课获奖课件.pptx

第五部分第五部分 图论图论本部分主要内容本部分主要内容l 图基本概念图基本概念l 欧拉图、哈密顿图欧拉图、哈密顿图l 树树l 平面图平面图l 支配集、覆盖集、独立集、匹配与着色支配集、覆盖集、独立集、匹配与着色1第1页第1页第十四章第十四章 图基本概念图基本概念主要内容主要内容图图通路与回路通路与回路图连通性图连通性图矩阵表示图矩阵表示图运算图运算预备知识预备知识多重集合多重集合元素能够重复出现集合元素能够重复出现集合无序集无序集A B=(x,y)|x A y B2第2页第2页14.1 图图定义定义14.1 无向图无向图G=,其中其中(1)V 为顶点集，元素称为为顶点集，元素称为顶点顶点(2)E为为V V 多重集，其元素称为无向边，简称多重集，其元素称为无向边，简称边边实例实例 设设 V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)则则 G=为一无向图为一无向图3第3页第3页有向图有向图定义定义14.2 有向图有向图D=,只需注意只需注意E是是V V 多重子集多重子集图图2表示是一个有向图，试写出它表示是一个有向图，试写出它V 和和 E 注意：图数学定义与图形表示，在同构（待叙）意义下注意：图数学定义与图形表示，在同构（待叙）意义下是一一相应是一一相应4第4页第4页相关概念相关概念1.图图 可用可用G泛指图（无向或有向）泛指图（无向或有向）V(G),E(G),V(D),E(D)n阶图阶图2.有限图有限图3.n 阶零图与平凡图阶零图与平凡图4.空图空图5.用用 ek 表示无向边或有向边表示无向边或有向边6.顶点与边关联关系顶点与边关联关系 关联、关联次数关联、关联次数 环环 孤立点孤立点7.顶点之间相邻与邻接关系顶点之间相邻与邻接关系5第5页第5页8.邻域与关联集邻域与关联集 v V(G)(G为无向图为无向图)v 关联集关联集 v V(D)(D为有向图为有向图)9.标定图与非标定图标定图与非标定图10.基图基图相关概念相关概念6第6页第6页多重图与简朴图多重图与简朴图定义定义14.3 (1)无向图中平行边及重数无向图中平行边及重数(2)有向图中平行边及重数（注意方向性）有向图中平行边及重数（注意方向性）(3)多重图多重图(4)简朴图简朴图在定义在定义14.3中定义简朴图是极其主要概念中定义简朴图是极其主要概念 7第7页第7页顶点度数顶点度数定义定义14.4 (1)设设G=为无向图为无向图,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)奇顶点度与偶度顶点奇顶点度与偶度顶点8第8页第8页定理定理14.1 设设G=为任意无向图，为任意无向图，V=v1,v2,vn,|E|=m,则则证证 G中每条中每条边边(包括包括环环)都有两个端点，因此在都有两个端点，因此在计计算算G中各中各顶顶点点度数之和度数之和时时，每条，每条边边均提供均提供2度，度，m 条条边边共提供共提供 2m 度度.本定理证实类似于定理本定理证实类似于定理14.1握手定理握手定理定理定理14.2 设设D=为任意有向图，为任意有向图，V=v1,v2,vn,|E|=m,则则9第9页第9页握手定理推论握手定理推论推论推论 任何图任何图(无向或有向无向或有向)中，奇度顶点个数是偶数中，奇度顶点个数是偶数.证证 设设G=为任意图，令为任意图，令 V1=v|v V d(v)为奇数为奇数 V2=v|v V d(v)为偶数为偶数 则则V1 V2=V,V1 V2=，由握手定理可知，由握手定理可知由于由于2m,均为偶数，因此均为偶数，因此 为偶数，但由于为偶数，但由于V1中中顶点度数为奇数，因此顶点度数为奇数，因此|V1|必为偶数必为偶数.10第10页第10页例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余度顶点，其余顶点度数均小于顶点度数均小于3，问，问G阶数阶数n为几？为几？解解 本题关键是应用握手定理本题关键是应用握手定理.设除设除3度与度与4度顶点外，尚有度顶点外，尚有x个顶点个顶点v1,v2,vx，则则 d(vi)2，i=1,2,x，于是得不等式于是得不等式 32 24+2x得得 x 4,阶数阶数 n 4+4+3=11.握手定理应用握手定理应用11第11页第11页图度数列图度数列1.V=v1,v2,vn为无向图为无向图G顶点集，称顶点集，称d(v1),d(v2),d(vn)为为G度数列度数列 2.V=v1,v2,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第12页第12页图同构图同构定义定义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.图之间同构关系含有自反性、对称性和传递性图之间同构关系含有自反性、对称性和传递性.能找到多条同构必要条件，但它们全不是充分条件：能找到多条同构必要条件，但它们全不是充分条件：边数相同，顶点数相同边数相同，顶点数相同;度数列相同度数列相同;对应顶点关联集及邻域元素个数相同，等等对应顶点关联集及邻域元素个数相同，等等 若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构判断两个图同构是个难题判断两个图同构是个难题13第13页第13页图同构实例图同构实例图中图中(1)与与(2)度数列相同，它们同构吗？为何？度数列相同，它们同构吗？为何？(1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.(1)(2)14第14页第14页n 阶完全图与竞赛图阶完全图与竞赛图定义定义14.6(1)n(n 1)阶无向完全图阶无向完全图每个顶点与其余顶点均相邻每个顶点与其余顶点均相邻无向简朴图，记作无向简朴图，记作 Kn.简朴性质：边数简朴性质：边数(2)n(n 1)阶阶有向完全图有向完全图每对顶点之间都有两条方向相每对顶点之间都有两条方向相反有向边有向简朴图反有向边有向简朴图.简朴性质：简朴性质：(3)n(n 1)阶阶竞赛图竞赛图基图为基图为Kn有向简朴图有向简朴图.简朴性质：边数简朴性质：边数 15第15页第15页n 阶阶 k 正则图正则图(1)为为K5，(2)为为3阶有向完全图，阶有向完全图，(3)为为4阶竞赛图阶竞赛图.(1)(2)(3)定义定义14.7 n 阶阶k正则图正则图=k 无向简朴图无向简朴图简朴性质：边数（由握手定理得）简朴性质：边数（由握手定理得）Kn是是 n 1正则图，正则图，彼得松图（见书上图彼得松图（见书上图14.3(1)所表示，记住它）所表示，记住它）16第16页第16页子图子图定义定义14.8 G=,G=(1)GG G 为为G子图子图，G为为G 母图母图(2)若若GG且且V=V，则称，则称G 为为G生成子图生成子图(3)若若VV或或EE，称，称G 为为G真子图真子图(4)V（VV且且V）导出子图导出子图，记作，记作GV(5)E（EE且且E）导出子图导出子图，记作，记作GE 17第17页第17页例例2 画出画出K4所有非同构生成子图所有非同构生成子图实例实例18第18页第18页补图补图定义定义14.9 设设G=为为n阶无向简朴图，以阶无向简朴图，以V为顶点集，以为顶点集，以所有使所有使G成为完全图成为完全图Kn添加边构成集合为边集图，称为添加边构成集合为边集图，称为G补补图图，记作，记作 .若若G ,则称则称G是是自补图自补图.相对于相对于K4,求上面图中所有图补图，并指出哪些是自补图求上面图中所有图补图，并指出哪些是自补图.问：互为自补图两个图边数有何关系？问：互为自补图两个图边数有何关系？19第19页第19页14.2 通路与回路通路与回路定义定义14.11 给定图给定图G=（无向或有向），（无向或有向），G中中顶点与顶点与边交替序列边交替序列 =v0e1v1e2elvl，vi 1,vi 是是 ei 端点端点.(1)通路与回路：通路与回路：为为通路通路；若；若 v0=vl，为为回路回路，l 为为回路长回路长 度度.(2)简朴通路与回路：所有边各异，简朴通路与回路：所有边各异，为为简朴通路简朴通路，又若，又若v0=vl，为为简朴回路简朴回路(3)初级通路初级通路(路径路径)与初级回路与初级回路(圈圈)：中所有顶点各异，中所有顶点各异，则称则称 为为初级通路初级通路(路径路径)，又若除，又若除v0=vl，所有顶点各不相，所有顶点各不相同且所有边各异，则称同且所有边各异，则称 为为初级回路初级回路(圈圈)(4)复杂通路与回路：有边重复出现复杂通路与回路：有边重复出现20第20页第20页几点阐明几点阐明表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法（在简朴图中）只用顶点表示法（在简朴图中）混合表示法混合表示法环（长为环（长为1圈）长度为圈）长度为1，两条平行边组成圈长度为，两条平行边组成圈长度为 2，无向简朴图中，圈长，无向简朴图中，圈长3，有向简朴图中圈长度，有向简朴图中圈长度2.不同圈（以长度不同圈（以长度3为例）为例）定义意义下定义意义下 无向图：图中长度为无向图：图中长度为l（l3）圈，定义意义下为）圈，定义意义下为2l个个 有向图：图中长度为有向图：图中长度为l（l3）圈，定义意义下为）圈，定义意义下为l个个 同构意义下：长度相同圈均为同构意义下：长度相同圈均为1个个试讨论试讨论l=3和和l=4情况情况21第21页第21页通路与回路长度通路与回路长度定理定理14.5 在在n 阶图阶图G中，若从顶点中，若从顶点vi 到到vj（vi vj）存在通路，）存在通路，则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 通路通路.推论推论 在在 n 阶图阶图G中，若从顶点中，若从顶点vi 到到 vj（vi vj）存在通路，则）存在通路，则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1初级通路（路径）初级通路（路径）.定理定理14.6 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到本身回路，则一到本身回路，则一定存在定存在vi 到本身长度小于或等于到本身长度小于或等于 n 回路回路.推论推论 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到本身简朴回路，则一到本身简朴回路，则一定存在长度小于或等于定存在长度小于或等于n 初级回路初级回路.22第22页第22页14.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连通连通23第23页第23页短程线与距离短程线与距离(3)短程线与距离短程线与距离 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)24第24页第24页无向图连通度无向图连通度1.删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联边去掉及关联边去掉 G V 从从G中删除中删除V 中所有顶点中所有顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E 中所有边中所有边 2.点割集与边割集点割集与边割集 点割集与割点点割集与割点定义定义14.16 G=,VV V 为为点割集点割集p(G V)p(G)且有极小性且有极小性 v为为割点割点v为点割集为点割集定义定义14.17 G=,EE E 是是边割集边割集p(G E)p(G)且有极小性且有极小性 e是是割边割边（桥）（桥）e为边割集为边割集25第25页第25页点割集与割点点割集与割点例例3 v1,v4，v6是点是点割集，割集，v6是割点是割点.v2,v5是点割集吗？是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，等是边割集，e8是是桥，桥，e7,e9,e5,e6 是边是边割割集吗？集吗？几点阐明：几点阐明：Kn中无点割集，中无点割集，Nn中既无点割集，也无边割集，其中中既无点割集，也无边割集，其中Nn为为 n 阶零图阶零图.若若G 连通，连通，E 为边割集，则为边割集，则 p(G E)=2，V 为点割集，为点割集，则则 p(G V)2 26第26页第26页点连通度与边连通度点连通度与边连通度定义定义14.18 G为连通非完全图为连通非完全图 点连通度点连通度 (G)=min|V|V 为点割集为点割集 要求要求 (Kn)=n 1 若若G非连通，非连通，(G)=0 若若 (G)k，则称，则称G为为 k-连通图连通图 定义定义14.19 设设G为连通图为连通图 边连通度边连通度(G)=min|E|E 为边割集为边割集 若若G非连通，则非连通，则(G)=0 若若(G)r，则称，则称G是是 r 边边-连通图连通图图中，图中，=1，它是，它是 1-连通图连通图 和和 1边边-连通图连通图27第27页第27页几点阐明几点阐明(Kn)=(Kn)=n 1G非连通，则非连通，则 =0若若G中有割点，则中有割点，则=1，若有桥，则，若有桥，则=1若若(G)=k,则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1若若(G)=r,则则G是是1-边连通图，边连通图，2-边连通图，边连通图，r-边连通边连通图，但不是图，但不是(r+s)-边连通图，边连通图，s 1,之间关系之间关系.定理定理7.5 (G)(G)(G)请画出一个请画出一个 无向简朴图无向简朴图28第28页第28页有向图连通性有向图连通性定义定义14.20 D=为有向图为有向图 vi vj（vi 可达可达 vj）vi 到到vj 有通路有通路 vi vj（vi 与与vj 相互可达）相互可达）性质性质 含有自反性含有自反性(vi vi)、传递性、传递性 含有自反性、对称性、传递性含有自反性、对称性、传递性 vi 到到vj 短程线与距离短程线与距离类似于无向图中，只需注意距离表示法不同类似于无向图中，只需注意距离表示法不同(无向图中无向图中d(vi,vj)，有向图中，有向图中d)及及 d无对称性无对称性29第29页第29页有向图连通性及分类有向图连通性及分类定义定义14.22 D=为有向图为有向图 D弱连通弱连通(连通连通)基图为无向连通图基图为无向连通图 D单向连通单向连通 vi,vj V，vivj 或或 vjvi D强连通强连通 vi,vj V，vivj易知，强连通易知，强连通单向连通单向连通弱连通弱连通判别法判别法定理定理14.8 D强连通当且仅当强连通当且仅当D中存在通过每个顶点至少一次中存在通过每个顶点至少一次回路回路定理定理14.9 D单向连通当且仅当单向连通当且仅当D中存在通过每个顶点至少一中存在通过每个顶点至少一次通路次通路30第30页第30页扩大路径法扩大路径法无向图中无向图中设设G=为为 n 阶无向图，阶无向图，E.设设 l 为为G中一条路径，若中一条路径，若此路径始点或终点与通路外顶点相邻，就将它们扩到通此路径始点或终点与通路外顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到通路两个端点不路中来，继续这一过程，直到最后得到通路两个端点不与通路外顶点相邻为止与通路外顶点相邻为止.设最后得到路径为设最后得到路径为 l+k（长度（长度为为 l 路径扩大成了长度为路径扩大成了长度为 l+k 路径），称路径），称 l+k为为“极大路极大路径径”，称使用此种办法证实问题办法为，称使用此种办法证实问题办法为“扩大路径法扩大路径法”.有向图中类似讨论，只需注意，在每步扩大中确保有向边方有向图中类似讨论，只需注意，在每步扩大中确保有向边方向一致性向一致性.31第31页第31页实例实例由某条路径扩大出极大路径不惟一，极大路径不一定是由某条路径扩大出极大路径不惟一，极大路径不一定是图中最长路径图中最长路径上图中，上图中，(1)中实线边所表示长为中实线边所表示长为2初始路径初始路径，(2),(3),(4)中实线边所表示都是它扩展成极大路径中实线边所表示都是它扩展成极大路径.还能找到另外极大路径吗？还能找到另外极大路径吗？(1)(2)(4)(3)32第32页第32页扩大路径法应用扩大路径法应用例例4 设设 G 为为 n（n 3）阶无向简朴图，）阶无向简朴图，2，证实，证实G 中存在中存在长度长度 +1 圈圈.证证 设设 =v0v1vl 是由初始路径是由初始路径 0 用扩大路径法得到极用扩大路径法得到极大路径，则大路径，则 l （为何？）（为何？）.由于由于v0 不与不与 外顶点相邻，又外顶点相邻，又 d(v0)，因而在，因而在 上除上除 v1外，至少还存在外，至少还存在 1个顶点与个顶点与 v0 相邻相邻.设设 vx 是离是离 v0 最远顶最远顶点，于是点，于是 v0v1vxv0 为为 G 中长度中长度 +1 圈圈.33第33页第33页二部图二部图定义定义14.23 设设 G=为一个无向图，若能将为一个无向图，若能将 V分成分成 V1和和V2(V1 V2=V，V1 V2=)，使得，使得 G 中每条边两个端点都是中每条边两个端点都是一个属于一个属于V1，另一个属于，另一个属于V2，则称，则称 G 为为二部图二部图(或称或称二分二分图图、偶图偶图等等)，称，称V1和和V2为为互补顶点子集互补顶点子集，常将二部图，常将二部图G记为记为.又若又若G是简朴二部图，是简朴二部图，V1中每个顶点均与中每个顶点均与V2中所有顶点相中所有顶点相邻，则称邻，则称G为为完全二部图完全二部图，记为，记为 Kr,s，其中，其中r=|V1|，s=|V2|.注意，注意，n 阶零图为二部图阶零图为二部图.34第34页第34页二部图判别法二部图判别法定理定理14.10 无向图无向图G=是是二部图二部图当且仅当当且仅当G中无奇圈中无奇圈 由定理由定理14.10可知图可知图9中各图都是二部图，哪些是完全二部中各图都是二部图，哪些是完全二部图？哪些图是同构？图？哪些图是同构？35第35页第35页14.4 图矩阵表示图矩阵表示无向图关联矩阵（对图无限制）无向图关联矩阵（对图无限制）定义定义14.24 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej关联次数，称关联次数，称(mij)n m为为G 关联矩阵关联矩阵，记为，记为M(G).性质性质36第36页第36页有向图关联矩阵（无环有向图）定义定义14.25 有向有向图图D=，令，令则称则称(mij)n m为为D关联矩阵关联矩阵，记为，记为M(D).(4)平行边相应列相同平行边相应列相同性质性质有向图关联矩阵37第37页第37页有向图邻接矩阵（无限制）有向图邻接矩阵（无限制）定义定义14.26 设有向图设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点令为顶点 vi 邻接到顶点邻接到顶点 vj 边条数，称为边条数，称为D邻接矩邻接矩阵阵，记作，记作A(D)，或简记为，或简记为A.性质性质 38第38页第38页推推论论 设设Bl=A+A2+Al（l 1），），则则 Bl中元素中元素为D中长度为 l 通路总数，定理定理14.11 设设 A为为有向有向图图 D 邻邻接矩接矩阵阵，V=v1,v2,vn为顶为顶点集，点集，则则 A l 次次幂幂 Al（l 1）中元素）中元素为D中vi 到vj长度为 l 通路数，其中为vi到本身长度为 l 回路数，而为为D中中长长度小于或等于度小于或等于 l 回路数回路数为为D中中长长度小于或等于度小于或等于 l 通路数通路数.邻接矩阵应用邻接矩阵应用为为D 中长度为中长度为 l 回路总数回路总数.39第39页第39页例例5 有向图有向图D如图所表示，求如图所表示，求 A,A2,A3,A4，并回答诸问题：，并回答诸问题：(1)D 中长度为中长度为1,2,3,4通路各有多少条？其中回路分别为多少通路各有多少条？其中回路分别为多少条？条？(2)D 中长度小于或等于中长度小于或等于4通路为多少条？其中有多少条回路？通路为多少条？其中有多少条回路？实例实例40第40页第40页(1)D中中长长度度为为1通路通路为为8条，其中有条，其中有1条是回路条是回路.D中中长长度度为为2通路通路为为11条，其中有条，其中有3条是回路条是回路.D中长度为中长度为3和和4通路分别为通路分别为14和和17条，回路分别条，回路分别 为为1与与3条条.(2)D中长度小于等于中长度小于等于4通路为通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解41第41页第41页定定义义14.27 设设D=为为有向有向图图.V=v1,v2,vn,令令 有向图可达矩阵（无限制）有向图可达矩阵（无限制）称称(pij)n n 为为D可达矩阵，记作可达矩阵，记作P(D)，简记为，简记为P.由于由于 vi V，vivi，因此，因此P(D)主对角线上元素全为主对角线上元素全为1.由定义不难看出由定义不难看出,D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵.下图所表示有向图下图所表示有向图 D 可达矩阵为可达矩阵为42第42页第42页第十四章第十四章 习题课习题课主要内容主要内容无向图、有向图、关联与相邻、简朴图、完全图、正则图、无向图、有向图、关联与相邻、简朴图、完全图、正则图、子图、补图；握手定理与推论；图同构子图、补图；握手定理与推论；图同构通路与回路及其分类通路与回路及其分类无向图连通性与连通度无向图连通性与连通度有向图连通性及其分类有向图连通性及其分类图矩阵表示图矩阵表示43第43页第43页基本要求基本要求深刻理解握手定理及推论内容并能灵活地应用它们深刻理解握手定理及推论内容并能灵活地应用它们深刻理解图同构、简朴图、完全图、正则图、子图、补图、深刻理解图同构、简朴图、完全图、正则图、子图、补图、二部图概念以及它们性质及互相之间关系二部图概念以及它们性质及互相之间关系记住通路与回路定义、分类及表示法记住通路与回路定义、分类及表示法深刻理解与无向图连通性、连通度相关诸多概念深刻理解与无向图连通性、连通度相关诸多概念会判别有向图连通性类型会判别有向图连通性类型纯熟掌握用邻接矩阵及其幂求有向图中通路与回路数办法，纯熟掌握用邻接矩阵及其幂求有向图中通路与回路数办法，会求可达矩阵会求可达矩阵 44第44页第44页19阶无向图阶无向图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）它们都满足要求）它们都满足要求.办法二：反证法办法二：反证法不然，由握手定理推论可知，不然，由握手定理推论可知，“G至多有至多有4个个5度顶点并且度顶点并且至多有至多有4个个6度顶点度顶点”，这与，这与G是是 9 阶图矛盾阶图矛盾.45第45页第45页2数组2,2,2,2,3,3能简朴图化吗？若能，画出尽也许多非同构图来.练习练习2只要能画出6 阶无向简朴图，就说明它可简朴图化.下图4个图都以此数列为度数列，请证实它们彼此不同构，都是K6子图.46第46页第46页用扩大路径法证实用扩大路径法证实.情况一：情况一：+.证实证实D中存在长度中存在长度 +1圈圈.设设 =v0v1vl为极大路径，则为极大路径，则l (为何为何?).由于由于d(v0)，因此在因此在 上存在上存在PLAY邻接到v0，于是情况二：情况二：+，只需注意，只需注意d+(vl)+.3设设D=为有向简朴图，已知为有向简朴图，已知 (D)2，+(D)0，(D)0，证实，证实D中存在长度中存在长度 max+,+1圈圈.为为D中长度中长度 +1有向圈有向圈练习练习347第47页第47页(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通路（不含回路）有多少条？通路（不含回路）有多少条？(7)D中长度为中长度为4回路有多少条？回路有多少条？(8)D中长度中长度 4通路有多少条？其中有几条是回路？通路有多少条？其中有几条是回路？(9)写出写出D可达矩阵可达矩阵.4有向图有向图D如图所表示，如图所表示，回答下列诸问：回答下列诸问：练习练习448第48页第48页解答解答(1)D中有中有3种非同构圈，长度分别为种非同构圈，长度分别为1,2,3，请画出它们图形，请画出它们图形.(2)D中有中有3种非圈非同构简朴回路，它们长度分别为种非圈非同构简朴回路，它们长度分别为 4,5,6.请画出它们图形来请画出它们图形来.(3)D是强连通（为何？）是强连通（为何？）为解为解(4)(8)，只需先求，只需先求D邻接矩阵前邻接矩阵前4次幂次幂.49第49页第49页(4)v1到到v4长度为长度为1,2,3,4通路数分别为通路数分别为0,0,2,2.其中只有长其中只有长度为度为4两条是非初级简朴通路（定义意义下），见下图所两条是非初级简朴通路（定义意义下），见下图所表示表示.解答解答50第50页第50页解答解答(5)v1到到v1长度为长度为1,2,3,4回路数分别为回路数分别为1,1,3,5.其中长度为其中长度为1是是初级初级(环环)；长度为；长度为2是复杂；长度为是复杂；长度为3中有中有1条是复杂，条是复杂，2条条是初级；长度为是初级；长度为4有有1条是复杂，有条是复杂，有4条是非初级简朴回路条是非初级简朴回路.请在图中行遍以上各回路请在图中行遍以上各回路.(6)长度为长度为4通路通路(不含回路不含回路)为为33条条.(7)长度为长度为4回路为回路为11条条.(8)长度长度 4通路通路88条，其中条，其中22条为回路条为回路.(9)4 4全全1矩阵矩阵.51第51页第51页