图的基本概念

1、1n主要内容q图的基本概念q欧拉图、哈密顿图与平面图q树第四部分 图论2n主要内容q图q通路与回路q图的连通性q图的矩阵表示q图的运算n预备知识q多重集合元素可以重复出现的集合q无序积A&B=x,y | xAy B第十四章 图的基本概念314.1 图定义14.1 无向图G = , 其中(1) V 为顶点集，元素称为顶点(2) E为VV 的多重集，其元素称为无向边，简称边实例 设 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则 G = 为一无向图4有向图定义14.2 有向图D

2、=, 只需注意E是VV 的多重子集图2表示的是一个有向图，试写出它的V 和 E5相关概念1. 图 可用G泛指图（无向的或有向的） V(G), E(G), |V(G)| , |E(G)| n阶图2. n 阶零图和平凡图3. 空图4. 用 ek 表示无向边或有向边5. 顶点与边的关联关系 关联、关联次数 环 孤立点6. 顶点之间的相邻关系6)()()(),()(|)(vvNvNvvuGEvuGVuuvNv的闭邻域的邻域)(|)(关联与veGEeevI)()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD的闭邻域的邻域

3、的先驱元集的后继元集7. 邻域与关联集 vV(G) (G为无向图) v 的关联集 vV(D) (D为有向图)9. 标定图与非标定图10. 基图相关概念7多重图与简单图定义14.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数（注意方向性） (3) 多重图 (4) 简单图（既无环，也无平行边）n在定义14.3中定义的简单图是极其重要的概念 8顶点的度数定义14.4 (1) 设G=为无向图, vV, v作为边端点的次数， 称为v的度数d(v), 简称度 (2) 设D=为有向图, vV, d+(v)v的出度 d(v)v的入度 d(v)=d+(v)+d(v)v的度或度数 (3) (G

4、)=maxd(v), (G)=mind(v) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇度顶点、偶度顶点与悬挂顶点9mvdnii2)(1mvdvdmvdniiniinii111)()(,2)(且定理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, 则10握手定理推论推论 任何图 (无向或有向) 中，奇度顶点的个数

5、是偶数.证 设G=为任意图，令 V1=v | vV d(v)为奇数 V2=v | vV d(v)为偶数 则V1V2=V, V1V2=，由握手定理可知由于2m, 均为偶数，所以 为偶数，但因为V1中顶点度数为奇数，所以|V1|必为偶数. 21)()()(2VvVvVvvdvdvdm2)(Vvvd1)(Vvvd11握手定理应用例2 （1）已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点? （2）已知无向图G有11条边, 2,3,4,5,6度顶点各一个, 其余顶点均为悬挂顶点，求G中悬挂顶点个数? 解 （1）设G有n个顶点. 由握手定理, 43+2(n4)21

6、0 解得 n8 （2）设G有x个悬挂顶点. 由握手定理, 2m=22= d(vi)=2+3+4+5+6+x=20+x 解得 x=212n 阶完全图与竞赛图定义14.6 (1) n (n1) 阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作 Kn.简单性质：边数(2) n (n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质： (3) n (n1) 阶竞赛图基图为Kn的有向简单图.简单性质：边数1,2) 1(nnnm1),1(2),1(nnnnm 1,2) 1(nnnm13子图定义14.8 G=, G=（同为有向/无向）(1) VV, EEG为G的子图，G为G的母

7、图, GG(2) 若VV或EE，称G为G的真子图(3) 若GG且V=V，则称G为G的生成子图(4) VV且V ，G中端点都在V中的边，共同组成的子图称为V的导出子图，记作GV(5) EE且E ，G中与E关联的顶点，共同组成的子图称为E的导出子图，记作GE14补图定义14.9 设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 .G1514.2 通路与回路定义14.11 给定图G=（无向或有向的），G中顶点与边的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端点.(1) 通路与回路： 为通路；若 v0=vl， 为回

8、路，l 为回路长度.(2) 简单通路与回路：所有边各异， 为简单通路，又若v0=vl， 为简单回路(3) 初级通路(路径)与初级回路(圈)： 中所有顶点各异，则称 为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所 有的边各异，则称 为初级回路(圈)(4) 复杂通路与回路：有边重复出现16通路与回路的长度定理14.5 在n 阶简单图G中，若从顶点vi 到vj（vivj）存在通路，则从vi 到 vj 存在长度小于或等于n1 的通路.推论 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通路，则从vi 到vj 存在长度小于或等于n1的初级通路（路径）.定理14.6 在一个n 阶图

9、G中，若存在 vi 到自身的回路，则一定存在vi 到自身长度小于或等于 n 的回路.推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一定存在长度小于或等于n 的初级回路.1714.3 图的连通性无向图的连通性(1) 顶点之间的连通关系：G=为无向图 若 vi 与 vj 之间有通路，则 vivj 是V上的等价关系 R=| u,v V且uv (2) G的连通性与连通分支 若u,vV，uv，则称G连通 V1,V2,Vk，称GV1, GV2, ,GVk为连通分支，其个数 p(G)=k (k1)； k=1，G连通18短程线与距离(3) 短程线与距离 u与v之间的短程线：uv，u与v之间长度最

10、短的通路 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)19无向图的连通度1. 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2. 点割集与边割集定义14.15 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义14.16 G=, EE E是边割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集20点割集与割点例3 v1,v4，v6是点割集，v6是割点. v2,

11、v5是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6 是边割集吗？几点说明：l Kn中无点割集，Nn中既无点割集，也无边割集，其中Nn为 n 阶零图. l 若G 连通，E为边割集，则 p(GE)=2，V为点割集，则 p(GV)2 21点连通度与边连通度定义14.18 G为连通非完全图 点连通度 (G) = min |V |V 为点割集 规定 (Kn) = n1 若G非连通，(G) = 0 若 (G)k，则称G为 k-连通图 定义14.19 设G为连通图 边连通度(G) = min|E|E为边割集 若G非连通，则(G) = 0 若(G)r，则称G是

12、 r 边-连通图图中， =1，它是 1-连通图 和 1边-连通图例：v1v2v3v4v5v6v7e1e2e3e5e4e6e7e8e9点割集：点割集：v3,v5,v2,v6；割点：；割点： v2 ，v6边割集：边割集：e3,e4,e4,e5,e1,e2,e3,e1,e2,e4,e9；桥：桥： e91-连通图，不是连通图，不是2-连通图；连通图；1边边-连通图，不是连通图，不是2边边-连通图。连通图。23有向图的连通性n定义14.20 D=为有向图 vi vj（vi 可达 vj）vi 到vj 有通路 vi vj（vi 与vj 相互可达）n性质 具有自反性(vi vi)、传递性 具有自反性、对称性、

13、传递性 nvi 到vj 的短程线与距离类似于无向图中，只需注意距离表示法的不同(无向图中d(vi,vj)，有向图中d) 及 d无对称性24有向图的连通性及分类n定义14.22 D=为有向图 D弱连通(连通)基图为无向连通图 D单向连通vi,vjV，vivj 或 vjvi D强连通vi,vjV，vivj易知，强连通单向连通弱连通n判别法定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次的回路定理14.9 D单向连通当且仅当D中存在经过每个顶点至少一次的通路判断判断下列有向图的连通性：下列有向图的连通性：D1D2D3D4D1：弱连通图；：弱连通图；D2：单向连通图；：单向连通图；D3：强连

14、通图；：强连通图；D4：非连通图；：非连通图；2、判断书上图、判断书上图14.1的连通性的连通性26连通子图定义定义设，为一简单有向图，且是的子图。对于某一性质而言，若没有其他包含的子图具有这种性质，则称子图是相对于该性质的极大子图。具有强连通性质的极大子图称为强连通子图；具有单向连通性质的极大子图称为单向连通子具有弱连通性质的极大子图称为弱连通子图。27二部图n定义14.23 设 G=为一个无向图，若能将 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分图、偶图等 )，称V1和V2为互补顶点子集，

15、常将二部图G记为. n又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|. n注意，n 阶零图为二部图. 图中各图都是二部图图中各图都是二部图2914.4 图的矩阵表示定义14.24 无向图G=，|V|=n，|E|=m，令 mij为 vi 与 ej的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 性质平行边的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2) 1 (,11mmnivdmmjmjiijimjijniij30jiijmjmjiijiijniijmnivdmvdmmjm,1

16、110)3(,.,2 , 1),(| 1|),(| 1|)2(),.,2 , 1(0) 1 (的终点为，不关联与，的始点为jijijiijevevevm10,1 定义14.25 有向图D=，令则称 (mij)nm为D的关联矩阵，记为M(D). (4) 平行边对应的列相同性质有向图的关联矩阵31有向图的邻接矩阵定义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),(

17、) 1 (1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij32推论推论 设设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（l1）中元素为D中vi 到vj长度为 l 的通路数，其中为vi到自身长度为 l 的回路数，而为为D中长度小于或等于中长度小于或等于 l 的回路数的回路数为为

18、D中长度小于或等于中长度小于或等于 l 的通路数的通路数. 邻接矩阵的应用邻接矩阵的应用为为D 中长度为中长度为 l 的回路总数的回路总数. 33例5 有向图D如图所示，回答诸问题：(1) D 中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？(2) D 中长度小于或等于4的通路为多少条？其中有多少条回路？实例实例34 1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中长度为1的通路为8条，其中有1条是回路. D中长度为2的通路为11条，其中有3条是回路. D中长度为3和4

19、的通路分别为14和17条，回路分别 为1与3条.(2) D中长度小于等于4的通路为50条，其中有8条是回路.实例求解实例求解35否则,0可达,1jiijvvp 1101110111110001P定义14.27 设D=为有向图. V=v1, v2, , vn, 令 有向图的可达矩阵称 (pij)nn 为D的可达矩阵，记作P(D)，简记为P. 由于viV，vivi，所以P(D)主对角线上的元素全为1. 由定义不难看出, D 强连通当且仅当 P(D)为全1矩阵. 下图所示有向图 D 的可达矩阵为36欧拉图历史背景：哥尼斯堡七桥问题与欧拉图不是欧拉图，不存在一笔画37欧拉图定义定义15.1 (1) 欧

20、拉通路经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路.(3) 欧拉图具有欧拉回路的图.(4) 半欧拉图具有欧拉通路而无欧拉回路的图.欧拉图的判定 n连通无向图G是欧拉图当且仅当G中每个顶点的度均为偶数。n连通无向图G具有欧拉通路当且仅当G有零个或两个奇度顶点。39Fleury算法算法：(1) 任取v0V(G)，令P0=v0. (2) 设Pi = v0e1v1e2eivi 已经行遍，按下面方法从 E(G)e1,e2,ei 中选取ei+1： (a) ei+1与vi 相关联； (b) 除非无别的边可供行遍，否则ei+1不应该为 Gi =

21、Ge1,e2,ei 中的桥. (3) 当 (2)不能再进行时，算法停止.可以证明算法停止时所得简单通路 Pm = v0e1v1e2emvm(vm=v0)为G 中一条欧拉回路. 用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条. 4041哈密顿图n历史背景：哈密顿周游世界问题与哈密顿图 (1) (2) 42哈密顿图与半哈密顿图定义15.2 (1) 哈密顿通路经过图中所有顶点一次仅一次的通路.(2) 哈密顿回路经过图中所有顶点一次仅一次的回路.(3) 哈密顿图具有哈密顿回路的图.(4) 半哈密顿图具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈

22、密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上43实例在上图中，(1),(2) 是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？44无向哈密顿图的一个必要条件定理15.6 设无向图G=是哈密顿图，对于任意V1V且V1，均有 p(GV1) |V1|证证 设设C为为G中一条哈密顿回路中一条哈密顿回路(1) p(C V1) |V1|(2) p(G V1) p(C V1) |V1| （因为（因为C G）推论 设无向图G=是半哈密顿图，对于任意的V1V且V1均有 p(GV1) |V1|+1证证

23、 令令 uv为为G中哈密顿通路，令中哈密顿通路，令G = G (u,v)，则，则G 为哈为哈密顿图密顿图. 于是于是 p(G V1) = p(G V1 (u,v) |V1|+145几点说明定理15.6中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）由定理15.6立刻可知，Kr,s当sr+1时不是哈密顿图. 易知Kr,r（r2）时都是哈密顿图，Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图.例2 设G为n阶无向连通简单图，若G中有割点或桥，则G不 是哈密顿图.证 设v为割点，则 p(Gv) 2|v|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的图（连

24、通的）均有割点.其实，本例对非简单连通图也对.46无向哈密顿图的一个充分条件定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj) n1 ()则G 中存在哈密顿通路. 证明线索：(1) 由()证G连通(2) = v1v2vl 为G中极大路径. 若l = n, 证毕. (3) 否则，证G 中存在过上所有顶点的圈C，由(1) 知C外顶点存在与C上某顶点相邻顶点，从而得比更长的路径，重复(2) (3) ，最后得G中哈密顿通路. 47推论推论 设G为n (n3) 阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有 d(vi)+d(vj) n （）则

25、G中存在哈密顿回路，从而G为哈密顿图.证明线索：由定理15.7得 = v1v2vn 为G中哈密顿通路. 若(v1,vn)E(G)，得证. 否则利用（）证明存在过v1, v2, vn的圈(哈密顿回路). 定理15.8 设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图. 48几点说明n定理15.7是半哈密顿图的充分条件，但不是必要条件. 长度为n1（n4）的路径构成的图不满足（）条件，但它显然是半哈密顿图n定理15.7的推论同样不是哈密顿图的必要条件，G为长为n的圈，不满足（）条件，但它当然是哈密顿图.n由定理15.7的推论可知，K

26、n（n3）均为哈密顿图.49判断某图是否为哈密顿图方法 n判断某图是否为哈密顿图至今还是一个难题.n总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.n1. 观察出哈密顿回路.例3 下图(周游世界问题)是哈密顿图,易知a b c d e f g h i j k l m n p q r s t a为图中的一条哈密顿回路.注意，此图不满足定理15.7推论条件.50n2满足定理15.7推论的条件（）.例4 完全图Kn (n3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n1) n（n3），所以Kn为哈密顿图. n3破坏定理15.6的条件的图不是哈密顿图.例5 在四分之一国际象棋盘（44方格组成）