图论基本概念.pptx

《图论基本概念.pptx》由会员分享，可在线阅读，更多相关《图论基本概念.pptx（52页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1绪论图论的作用：l图与计算机：计算机中数据结构，离不开数组、串、各种链接表、树和图，因此图是计算机中数据表示、存储和运算的基础 l图与网络：最大流问题：假设从城市P到城市Q的一个公路网，公路网中每段公路上每天可以通过的汽车的数量有上限，那么经过该公路网，每天最多可以有多少辆汽车从城市P开到城市Q？最优支撑树问题：某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？第1页/共52页2第十四章 图的基本概念主要内容l图l

2、通路与回路l图的连通性l图的矩阵表示l图的运算预备知识l多重集合元素可以重复出现的集合l无序集AB=(x,y)|xAyB第2页/共52页314.1 图定义14.1 无向图G=,其中(1)V 为顶点集，元素称为顶点 Vertex(2)E为VV 的多重集，其元素称为无向边，简称边 Edge实例 设 V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)则 G=为一无向图第3页/共52页4有向图定义14.2 有向图D=,只需注意E是VV 的多重子集图2表示的是一个有向图，试写出它的V 和 E 注意：图的数学定义与图形表

3、示，在同构（待叙）的意义下是一一对应的第4页/共52页5相关概念1.图 可用G泛指图（无向的或有向的）V(G),E(G),|V(G)|,|E(G)|n阶图：n 个顶点的图2.有限图3.n 阶零图（0条边）与平凡图（1个顶点）4.空图（运算中出现）5.用 ek 表示无向边或有向边第5页/共52页6相关概念6.顶点与边的关联关系 关联、关联次数 环 孤立点7.顶点之间的相邻与邻接关系第6页/共52页78.邻域与关联集 v V(G)(G为无向图)v 的关联集 v V(D)(D为有向图)9.标定图与非标定图(顶点和边指定编号的）10.基图（有向图的有向边改为无向边）相关概念第7页/共52页8多重图与简

4、单图定义14.3 (1)无向图中的平行边及重数 关联一对顶点的边多于一条，条数称为重数(2)有向图中的平行边及重数（注意方向性）(3)多重图(4)简单图（无平行边和环）简单图是极其重要的概念 第8页/共52页9顶点的度数定义14.4 (1)设G=为无向图,vV,d(v)v的度数,简称度 (2)设D=为有向图,vV,d+(v)v的出度 d(v)v的入度 d(v)v的度或度数 (3)(G)（最大度）,(G)（最小度）无向图中 (4)+(D),+(D),(D),(D),(D),(D)(5)度数为1的点称为悬挂点，关联的边为悬挂边；奇顶点度与偶度顶点第9页/共52页10定理定理14.1 设设G=为任意

5、无向图，为任意无向图，V=v1,v2,vn,|E|=m,则则证 G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m 条边共提供 2m 度.此二定理是欧拉此二定理是欧拉17361736年给出，是图论的基本定理年给出，是图论的基本定理握手定理定理14.2 设D=为任意有向图，V=v1,v2,vn,|E|=m,则第10页/共52页11握手定理推论推论 任何图(无向或有向)中，奇度顶点的个数是偶数.证 设G=为任意图，令 V1=v|vV d(v)为奇数 V2=v|vV d(v)为偶数 则V1V2=V,V1V2=，由握手定理可知由于2m,均为偶数，所以 为偶数，但因为

6、V1中顶点度数为奇数，所以|V1|必为偶数.第11页/共52页12图的度数列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)都不是可简单图化的，特别是后者也不是可图化的

7、第12页/共52页13图的同构定义14.5 设G1=,G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1 当且仅当(f(vi),f(vj)E2 （E1 当且仅当 E2)并且,(vi,vj)（）与(f(vi),f(vj)（）的重数相同，则称G1与G2是同构的，记作G1G2.l图之间的同构关系具有自反性、对称性和传递性.l能找到多条同构的必要条件，但它们全不是充分条件：边数相同，顶点数相同;度数列相同;对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构l判断两个图同构是个难题第13页/共52页14图同构的实例图中(1)与(2)

8、的度数列相同，它们同构吗？为什么？(1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.(1)(2)第14页/共52页15n 阶完全图与竞赛图定义14.6(1)n(n1)阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作 Kn.简单性质：边数(2)n(n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质：(3)n(n1)阶竞赛图基图为Kn的有向简单图.简单性质：边数 第15页/共52页16n 阶 k 正则图(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图.(1)(2)(3)定义14.7 n 阶k正则图=k 的无向简单图简单

9、性质：边数（由握手定理得）Kn是 n 1正则图，彼得松图（见书上图14.3(1)所示，记住它）第16页/共52页17子图定义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页/共52页18例2 画出K4的所有非同构的生成子图实例第18页/共52页19补图定义14.9 设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 .若G ,则称G是自补图.相对于K4,求上面图

10、中所有图的补图，并指出哪些是自补图.问：互为自补图的两个图的边数有何关系？第19页/共52页2014.2 通路与回路定义14.11 给定图G=（无向或有向的），G中顶点与边的交替序列 =v0e1v1e2elvl，vi1,vi 是 ei 的端点.(1)通路与回路：为通路；若 v0=vl，为回路，l 为回路长 度.(2)简单通路与回路：所有边各异，为简单通路，又若v0=vl，为简单回路(3)初级通路(路径)与初级回路(圈)：中所有顶点各异，则称 为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称 为初级回路(圈)(4)复杂通路与回路：有边重复出现第20页/共52页21几点

11、说明表示法 定义表示法 只用边表示法 只用顶点表示法（在简单图中）混合表示法环（长为1的圈）的长度为1，两条平行边构成的圈长度为 2，无向简单图中，圈长3，有向简单图中圈的长度2.不同的圈（以长度3的为例）定义意义下 无向图：图中长度为l（l3）的圈，定义意义下为2l个 有向图：图中长度为l（l3）的圈，定义意义下为l个 同构意义下：长度相同的圈均为1个试讨论l=3和l=4的情况第21页/共52页22通路与回路的长度定理14.5 在n 阶图G中，若从顶点vi 到vj（vivj）存在通路，则从vi 到 vj 存在长度小于或等于n1 的通路.推论 在 n 阶图G中，若从顶点vi 到 vj（vivj

12、）存在通路，则从vi 到vj 存在长度小于或等于n1的初级通路（路径）.定理14.6 在一个n 阶图G中，若存在 vi 到自身的回路，则一定存在vi 到自身长度小于或等于 n 的回路.推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一定存在长度小于或等于n 的初级回路.第22页/共52页2314.3 图的连通性无向图的连通性(1)顶点之间的连通关系：G=为无向图 若 vi 与 vj 之间有通路，则 vivj 是V上的等价关系 R=|u,v V且uv(2)G的连通性与连通分支 若u,vV，uv，则称G连通 V/R=V1,V2,Vk，称GV1,GV2,GVk为连通分 支，其个数 p(G

13、)=k (k1)；k=1，G连通第23页/共52页24短程线与距离(3)短程线与距离 u与v之间的短程线：uv，u与v之间长度最短的通路 u与v之间的距离：d(u,v)短程线的长度 d(u,v)的性质：d(u,v)0,uv时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)第24页/共52页25无向图的连通度1.删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2.点割集与边割集 点割集与割点定义14.16 G=,VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义14.17 G

14、=,EE E是边割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集第25页/共52页26点割集与割点例3 v1,v4，v6是点割集，v6是割点.v2,v5是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6 是边割集吗？几点说明：lKn中无点割集，Nn中既无点割集，也无边割集，其中Nn为 n 阶零图.l若G 连通，E 为边割集，则 p(G E)=2，V 为点割集，则 p(G V)2 第26页/共52页27点连通度与边连通度定义14.18 G为连通非完全图 点连通度(G)=min|V|V 为点割集 规定(Kn)=n1 若G非连通，(G)=0 若

15、(G)k，则称G为 k-连通图 定义14.19 设G为连通图 边连通度(G)=min|E|E为边割集 若G非连通，则(G)=0 若(G)r，则称G是 r 边-连通图图中，=1，它是 1-连通图 和 1边-连通图第27页/共52页28几点说明l(Kn)=(Kn)=n1lG非连通，则=0l若G中有割点，则=1，若有桥，则=1l若(G)=k,则G是1-连通图，2-连通图，k-连通图，但不是(k+s)-连通图，s1l若(G)=r,则G是1-边连通图，2-边连通图，r-边连通图，但不是(r+s)-边连通图，s1l,之间的关系.定理7.5 (G)(G)(G)请画出一个的无向简单图第28页/共52页29有向

16、图的连通性定义14.20 D=为有向图 vi vj（vi 可达 vj）vi 到vj 有通路 vi vj（vi 与vj 相互可达）性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性 vi 到vj 的短程线与距离类似于无向图中，只需注意距离表示法的不同(无向图中d(vi,vj)，有向图中d)及 d无对称性第29页/共52页30有向图的连通性及分类定义14.22 D=为有向图 D弱连通(连通)基图为无向连通图 D单向连通vi,vjV，vivj 或 vjvi D强连通vi,vjV，vivj易知，强连通单向连通弱连通判别法定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次的回路定

17、理14.9 D单向连通当且仅当D中存在经过每个顶点至少一次的通路第30页/共52页31扩大路径法无向图中设G=为 n 阶无向图，E.设 l 为G中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止.设最后得到的路径为l+k（长度为 l 的路径扩大成了长度为 l+k 的路径），称l+k为“极大路径”，称使用此种方法证明问题的方法为“扩大路径法”.有向图中类似讨论，只需注意，在每步扩大中保证有向边方向的一致性.第31页/共52页32实例由某条路径扩大出的极大路径不惟一，极大路径不一定是图中最长的路径上图中，(1

18、)中实线边所示的长为2的初始路径，(2),(3),(4)中实线边所示的都是它扩展成的极大路径.还能找到另外的极大路径吗？(1)(2)(4)(3)第32页/共52页33扩大路径法的应用例4 设 G 为 n（n3）阶无向简单图，2，证明G 中存在长度 +1 的圈.证 设 =v0v1vl 是由初始路径 0 用扩大路径法的得到的极大路径，则 l （为什么？）.因为v0 不与 外顶点相邻，又 d(v0)，因而在 上除 v1外，至少还存在 1个顶点与 v0 相邻.设 vx 是离 v0 最远的顶点，于是 v0v1vxv0 为 G 中长度 +1 的圈.第33页/共52页34二部图定义14.23 设 G=为一个

19、无向图，若能将 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是一个属于V1，另一个属于V2，则称 G 为二部图(或称二分图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|.注意，n 阶零图为二部图.第34页/共52页35二部图的判别法定理14.10 无向图G=是二部图当且仅当G中无奇圈 由定理14.10可知图9中各图都是二部图，哪些是完全二部图？哪些图是同构的？第35页/共52页3614.4 图的矩阵表示无向图的关联矩阵（对

20、图无限制）定义14.24 无向图G=，|V|=n，|E|=m，令 mij为 vi 与 ej的关联次数，称(mij)nm为G 的关联矩阵，记为M(G).性质第36页/共52页37有向图的关联矩阵（无环有向图）定义定义14.25 有向图D=，令则称(mij)n m为D的关联矩阵，记为M(D).(4)平行边对应的列相同平行边对应的列相同性质有向图的关联矩阵第37页/共52页38有向图的邻接矩阵（无限制）定义14.26 设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点 vi 邻接到顶点 vj 边的条数，称为D的邻接矩阵，记作A(D)，或简记为A.性质 第38页/共52页39推论 设B

21、l=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页/共52页40例5 有向图D如图所示，求 A,A2,A3,A4，并回答诸问题：(1)D 中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D 中长度小于或等于4的通路为多少条？其中有多

22、少条回路？实例第40页/共52页41(1)D中长度为1的通路为8条，其中有1条是回路.D中长度为2的通路为11条，其中有3条是回路.D中长度为3和4的通路分别为14和17条，回路分别 为1与3条.(2)D中长度小于等于4的通路为50条，其中有8条是回路.实例求解第41页/共52页42定义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页/共52页43

23、第十四章 习题课主要内容l无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构l通路与回路及其分类l无向图的连通性与连通度l有向图的连通性及其分类l图的矩阵表示第43页/共52页44基本要求l深刻理解握手定理及推论的内容并能灵活地应用它们l深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系l记住通路与回路的定义、分类及表示法l深刻理解与无向图连通性、连通度有关的诸多概念l会判别有向图连通性的类型l熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵 第44页/共52页4519阶无向图G中，每个顶点的度

24、数不是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页/共52页462数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的非同构的图来.练习2只要能画出6 阶无向简单图，就说明它可简单图化.下图的4个图都以此数列为度数列，请证明它们彼此不同

25、构，都是K6的子图.第46页/共52页47用扩大路径法证明.情况一：+.证明D中存在长度 +1的圈.设 =v0v1vl为极大路径，则l (为什么?).由于d(v0)，所以在 上存在PLAY邻接到v0，于是情况二：+，只需注意d+(vl)+.3设D=为有向简单图，已知 (D)2，+(D)0，(D)0，证明D中存在长度 max+,+1的圈.为D中长度 +1的有向圈练习3第47页/共52页48(1)D中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？(3)D是哪类连通图?(4)D中v1到v4长度为1,2,3,4的通路各多少 条？其中几条是非初级的简单通路？(5)D中v1到v1长度为1,2,3

26、,4的回路各多少 条？讨论它们的类型.(6)D中长度为4的通路（不含回路）有多少条？(7)D中长度为4的回路有多少条？(8)D中长度4的通路有多少条？其中有几条是回路？(9)写出D的可达矩阵.4有向图D如图所示，回答下列诸问：练习4第48页/共52页49解答(1)D中有3种非同构的圈，长度分别为1,2,3，请画出它们的图形.(2)D中有3种非圈的非同构的简单回路，它们的长度分别为 4,5,6.请画出它们的图形来.(3)D是强连通的（为什么？）为解(4)(8)，只需先求D的邻接矩阵的前4次幂.第49页/共52页50(4)v1到v4长度为1,2,3,4的通路数分别为0,0,2,2.其中只有长度为4的两条是非初级的简单通路（定义意义下），见下图所示.解答第50页/共52页51解答(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)44的全1矩阵.第51页/共52页52感谢您的观看！第52页/共52页