图的基本概念讲稿.ppt

《图的基本概念讲稿.ppt》由会员分享，可在线阅读，更多相关《图的基本概念讲稿.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本概念第一页，讲稿共八十九页哦第二页，讲稿共八十九页哦第十四章 图的基本概念第三页，讲稿共八十九页哦无序积与多重集合无序积与多重集合 设A，B为任意的两个集合，称a,b|aAbB为A与B的无序积，记作A&B。可将无序积中的无序对a,b记为(a,b)，并且允许ab。无论a,b是否相等，均有(a,b)(b,a)，因而A&BB&A。元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如 在多重集合a,a,b,b,b,c,d中，a,b,c,d的重复度分别为2,3,1,1。第四页，讲稿共八十九页哦第一节 图第五页，讲稿共八十九页哦例14.1(1)给定无向图G，其

2、中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)给定有向图D=，其中 Va,b,c,d，E,。画出G与D的图形。第六页，讲稿共八十九页哦关于图的一些概念和规定关于图的一些概念和规定G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。V(G)，E(G)分别表示G的顶点集和边集。若|V(G)|n，则称G为n阶图。若|V(G)|与|E(G)|均为有限数，则称G为有限图。若边集E(G)，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。在图

3、的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。第七页，讲稿共八十九页哦标定图与非标定图、基图 将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。第八页，讲稿共八十九页哦关联与关联次数、环、孤立点 设G为无向图，ek(vi,vj)E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相

4、关联的。若vivj，则称ek与vi或ek与vj的关联次数为1。若vivj，则称ek与vi的关联次数为2，并称ek为环。任意的vlV，若vlvi且vlvj，则称ek与vl的关联次数为0。设D为有向图，ekE，称vi,vj为ek的端点。若vivj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。第九页，讲稿共八十九页哦相邻与邻接 设无向图G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D，vi，vjV，ek，elE。若etE，使得et，则称vi为et的始点，vj为

5、et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。第十页，讲稿共八十九页哦邻域设无向图G，vV，称u|uV(u,v)Euv为v的邻域，记做NG(v)。称NG(v)v为v的闭邻域，记做NG(v)。称e|eEe与v相关联为v的关联集，记做IG(v)。设有向图D，vV，称u|uVEuv为v的后继元集，记做+D(v)。称u|uVEuv为v的先驱元集，记做-D(v)。称+D(v)-D(v)为v的邻域，记做ND(v)。称ND(v)v为v的闭邻域，记做ND(v)。第十一页，讲稿共八十九页哦举例举例NG(v1)+D(d)v2 2，v5 5 NG(v1)v1 1，v2

6、 2，v5 5 I IG G(v1 1)e1 1，e2 2，e3 3 c-D(D(d)a，c N ND D(d)a，c N ND D(d)a，c，d 第十二页，讲稿共八十九页哦第十三页，讲稿共八十九页哦第十四页，讲稿共八十九页哦图的度数的相关概念在无向图G中，最大度(G)maxd(v)|vV(G)最小度(G)mind(v)|vV(G)在有向图D中，最大出度+(D)maxd+(v)|vV(D)最小出度+(D)mind+(v)|vV(D)最大入度-(D)maxd-(v)|vV(D)最小入度-(D)mind-(v)|vV(D)称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点

7、称为偶度(奇度)顶点。第十五页，讲稿共八十九页哦图的度数举例d(v1)4(注意，环提供2度)，4，1，v4是悬挂顶点，e7是悬挂边。d+(a)4，d-(a)1(环e1提供出度1，提供入度1)，d(a)4+15。5，3，+4(在a点达到)+0(在b点达到)-3(在b点达到)-1(在a和c点达到)第十六页，讲稿共八十九页哦第十七页，讲稿共八十九页哦第十八页，讲稿共八十九页哦问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明

8、：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。第十九页，讲稿共八十九页哦度数列设G为一个n阶无向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列dd1,d2,dn，若存在Vv1,v2,vn为顶点集的n阶无向图G，使得d(vi)di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。类似地，设D为一个n阶有向图，Vv1,v2,vn，称d(v1)，d(v2)，d(vn)为D的度数列，另外称d

9、+(v1)，d+(v2)，d+(vn)与d-(v1)，d-(v2)，d-(vn)分别为D的出度列和入度列。第二十页，讲稿共八十九页哦度数列举例按顶点的标定顺序，度数列为4,4,2,1,3。按字母顺序，度数列，出度列，入度列按字母顺序，度数列，出度列，入度列分别为分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2第二十一页，讲稿共八十九页哦第二十二页，讲稿共八十九页哦定理14.3的证明由握手定理可知必然性显然。下面证明充分性。由已知条件可知，d中有2k(0kn/2)个奇数，不妨设它们为d1，d2，dk，dk+1，dk+2，d2k。可用多种方法做出n阶无向图

10、G，Vv1,v2,vn。比如边集如下产生：在顶点vr与vr+k之间连边，r1,2,k。若di为偶数，令didi，若di为奇数，令didi-1，得d(d1，d2，dn)，则di均为偶数。再在vi处做出di/2条环,i1,n，将所得各边集合在一起组成E，则G的度数列为d。其实，di为偶数时，d(vi)2di/22di/2di，当di为奇数时，d(vi)1+2di/21+di1+di-1di，这就证明了d是可图化的。第二十三页，讲稿共八十九页哦定理定理14.414.4 设设G G为任意为任意n n阶无向简单图，则阶无向简单图，则(G)(G)n n-1-1。第二十四页，讲稿共八十九页哦第二十五页，讲稿

11、共八十九页哦图的同构举例彼得森彼得森(Petersen)图图第二十六页，讲稿共八十九页哦第二十七页，讲稿共八十九页哦2图之间的同构关系是等价关系 图之间的同构关系 可看成全体图集合上的二元关系，这个二元关系 具有自反性，对称性和传递性，因而它是等价关系。在这个等价关系的每一等价类中均取一个非标定图作为一个代表，凡与它同构的图，在同构的意义之下都可以看成一个图，在上面图中，(1)，(2)，(3)可以看成一个图，它们都是彼得松图，其中的(1)可看成这类图的代表。提到彼得松图，一般是指(1)中图。第二十八页，讲稿共八十九页哦 至此，可以这样说，在图同构的意义下，图的数学定义与图形表示是一一对应的。关

12、于图之间的同构问题还应该指出以下两点：a到目前为止，人们还没有找到判断两个图是否同构的好的算法，还只能根据定义看是否能找到满足条件的双射函数，显然这是困难的。第二十九页，讲稿共八十九页哦 b需要注意的是，不要将两个图同构的必要条件当成充分条件。若G1 G2，则它们的阶数相同，边数相同，度数列相同，等等。破坏这些必要条件的任何一个，两个图就不会同构，但以上列出的条件都满足，两个图也不一定同构，在图14.2中的两个图，有相同的度数列，但它们不同构。第三十页，讲稿共八十九页哦第三十一页，讲稿共八十九页哦第三十二页，讲稿共八十九页哦第三十三页，讲稿共八十九页哦第三十四页，讲稿共八十九页哦第三十五页，讲

13、稿共八十九页哦例14.3(1)画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：(1)2，2，1，1(2)3，1，1，1(3)2，2，2，0 将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。第三十六页，讲稿共八十九页哦例14.3(2)画出3阶2条边的所有非同构的有向简单图。由握手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2。

14、度数列及入度出度列为1,2,1入度列为入度列为 0,1,1 0,1,1 或或 0,2,0 0,2,0 或或 1,0,11,0,1出度列为出度列为 1,1,0 1,1,0 或或 1,0,1 1,0,1 或或 0,2,00,2,02,2,0入度列为入度列为 1,1,01,1,0出度列为出度列为 1,1,01,1,0第三十七页，讲稿共八十九页哦第三十八页，讲稿共八十九页哦第三十九页，讲稿共八十九页哦第四十页，讲稿共八十九页哦举例GGe5G e1,e4 Gv5G v4,v5 G e5第四十一页，讲稿共八十九页哦第二节 通路与回路第四十二页，讲稿共八十九页哦第四十三页，讲稿共八十九页哦n阶图中通路与回路

15、的性质定理14.5 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n-1的通路。证明:设v0e1v1e2elvl(v0vi,vlvj)为G中一条长度为l的通路，若ln-1，则满足要求，否则必有l+1n，即上的顶点数大于G中的顶点数，于是必存在k,s,0ksl，使得 vsvk,即在上存在vs到自身的回路Csk,在上删除Csk上的一切边及除vs外的一切顶点，得v0e1v1e2vkes+1 elvl,仍为vi到vj的通路，且长度至少比减少1。若还不满足要求，则重复上述过程，由于G是有限图，经过有限步后，必得到vi到vj长度小于或等于n-1的通路。第四十四页，讲

16、稿共八十九页哦推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。定理14.6 在一个n阶图G中，若存在vi 到自身的回路，则一定存在vi 到自身长度小于或等于n的回路。推论 在一个n阶图G中，若存在vi 到自身的简单回路，则一定存在vi 到自身长度小于或等于n的初级回路。第四十五页，讲稿共八十九页哦例14.4 无向完全图Kn(n3)中有几种非同构的圈？解答长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，易知Kn(n3)中含长度为3，4，n的圈，所以Kn(n3)中有n-2种非同构的圈。第四十六页，讲稿共八十九页哦例1

17、4.5 无向完全图K3的顶点依次标定为a,b,c。在定义意义下K3中有多少个不同的圈？解答在同构意义下，K3中只有一个长度为3的圈。但在定义意义下，不同起点(终点)的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同的长为3的圈：abca，acba，bacb，bcab，cabc，cbac如果只考虑起点(终点)的差异，而不考虑顺时针逆时针的差异，应有3种不同的圈，当然它们都是同构的，画出图来只有一个。第四十七页，讲稿共八十九页哦第三节 图的连通性第四十八页，讲稿共八十九页哦第四十九页，讲稿共八十九页哦第五十页，讲稿共八十九页哦第五十一页，讲稿共八十九页哦第五十二页，讲稿共八十

18、九页哦第五十三页，讲稿共八十九页哦第五十四页，讲稿共八十九页哦K4 4K3 3K2 2K1 1K=1=21=2K2 2K0 0K0 0第五十五页，讲稿共八十九页哦第五十六页，讲稿共八十九页哦第五十七页，讲稿共八十九页哦第五十八页，讲稿共八十九页哦第五十九页，讲稿共八十九页哦第六十页，讲稿共八十九页哦例14.8 设G为n（n4）阶无向简单图，(G)3。证明G中存在长度大于或等于4的圈。证明 不妨设G是连通图，否则，因为G的各连通分支的最小度也都大于或等于3，因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点，由G是连通图，因而u,v之间存在通路，由定理14.5的推论可知，u,v之间存在

19、路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为lv0v1vl，易知l3。若v0与vl相邻，则l(v0,vl)为长度大于或等于4的圈。否则，由于d(v0)(G)3，因而v0除与l上的v1相邻外，还存在l上的顶点vk(k1)和vt(kt l)与v0相邻，则v0v1vkvtv0为一个圈且长度大于或等于4，见图。第六十一页，讲稿共八十九页哦第六十二页，讲稿共八十九页哦二部图举例K6的子图的子图K6的子图的子图K3,3K2,3K3,3K2,3第六十三页，讲稿共八十九页哦二部图的判定定理定理14.10 一个无向图G是二部图当且仅当G中无奇数长度的回路。证明必要性。若G中无回路，结论显然成立

20、。若G中有回路，只需证明G中无奇圈。设C为G中任意一圈，令Cvi1vi2vilvi1，易知 l2。不妨设vi1V1，则必有vilV-V1=V2，而l必为偶数，于是C为偶圈，由C的任意性可知结论成立。第六十四页，讲稿共八十九页哦充分性。不妨设G为连通图，否则可对每个连通分支进行讨论。设v0为G中任意一个顶点，令V1v|vV(G)d(v0,v)为偶数V2v|vV(G)d(v0,v)为奇数易知，V1,V2,V1V2，V1V2V(G)。下面只要证明V1中任意两顶点不相邻,V2中任意两点也不相邻。若存在vi,vjV1相邻，令(vi,vj)e，设v0到vi,vj的短程线分别为i,j，则它们的长度d(v0,

21、vi),d(v0,vj)都是偶数，于是ije中一定含奇圈，这与已知条件矛盾。类似可证，V2中也不存在相邻的顶点，于是G为二部图。第六十五页，讲稿共八十九页哦第四节 图的矩阵表示第六十六页，讲稿共八十九页哦 e1 e2 e3 e4 e5V1V2V3v4第六十七页，讲稿共八十九页哦第六十八页，讲稿共八十九页哦第六十九页，讲稿共八十九页哦第七十页，讲稿共八十九页哦v v1 1 v v2 2 v v3 3 v v4 4v v1 1 v v2 2 v v3 3 v v4 4第七十一页，讲稿共八十九页哦第七十二页，讲稿共八十九页哦第七十三页，讲稿共八十九页哦第七十四页，讲稿共八十九页哦第七十五页，讲稿共八

22、十九页哦14.5 图的运算定义14.28 设G1，G2为两个图。若V1V2，则称G1与G2是不交的。若E1E2，则称G1与G2是边不交的或边不重的。说明：不交的图，必然是边不交的，但反之不真。第七十六页，讲稿共八十九页哦图的运算定义14.29 设G1，G2为不含孤立点的两个图（它们同为无向图或同为有向图）。(1)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的并图，记作G1G2。(2)称以E1-E2为边集，以E1-E2中边关联的顶点组成的集合为顶点集的图为G1与G2的差图，记作G1-G2。(3)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为

23、G1与G2的交图，记作G1G2。(4)称以E1E2为边集（为集合之间的对称差运算），以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的环和，记作G1G2。第七十七页，讲稿共八十九页哦定义14.29的说明(1)若G1G2，则G1G2G1G2G1(G2)G1-G2G2-G1G1G2这就是在图的定义中给出空图概念的原因。(2)当G1与G2边不重时，G1G2G1-G2G1G2-G1G2 G1G2G1G2(3)图之间环和的定义也可以用并、交、差给出，即G1G2(G1G2)-(G1G2)第七十八页，讲稿共八十九页哦第十四章 习题课第七十九页，讲稿共八十九页哦第八十页，讲稿共八十九页哦第八十一页，讲稿共八十九页哦第八十二页，讲稿共八十九页哦第八十三页，讲稿共八十九页哦PLAY第八十四页，讲稿共八十九页哦第八十五页，讲稿共八十九页哦第八十六页，讲稿共八十九页哦解 第八十七页，讲稿共八十九页哦第八十八页，讲稿共八十九页哦第八十九页，讲稿共八十九页哦