离散数学_第七章_图论.ppt

《离散数学_第七章_图论.ppt》由会员分享，可在线阅读，更多相关《离散数学_第七章_图论.ppt（337页珍藏版）》请在金锄头文库上搜索。

1、1,第7章 图 论,离 散 数 学,济南大学,信息科学与工程学院,第2页,第7章 图,7.1 图的基本概念 7.2 路与回路 7.3 图的矩阵表示 7.4 汉密尔顿图和欧拉图 7.5 平面图 7.6 对偶图和着色 7.7 树 7.8 根树,第3页,本章学习要求,第4页,引例1 哥尼斯堡七桥问题,1736年瑞士数学家列昂哈德欧拉(leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。这个问题是这样的： 哥尼斯堡(Knigsberg)城市有一条横贯全城的普雷格尔(PreGel)河，城的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，能不能设计一次“逛

2、游”，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。,第5页,g,f,a,b,c,d,e,引例1 哥尼斯堡七桥问题,现实问题抽象成图 若想完成逛游，需要添加几座桥，如何建？,第6页,引例2 周游世界问题,1859年威廉汉密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏，能不能在图中找到一条回路，使它含有这个图的全部结点？ 他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。,第7页,引例3 四色问题(Four Color Proble

3、m),1852, Francis Guthrie（格色里）, 注意到英格兰地图可以用4种颜色染色, 使得相邻面(有一段公共边界,不只是有一个公共点)有不同颜色; 他问其弟 Frederick 是否任意地图都有此性质?,第8页,韦尔奇.鲍威尔法,第9页,知识点： 图的基本概念 点与边的关联、点（边）相邻 完全图、补图，子图、生成子图 点度数 握手定理 图的同构,7-1 图的基本概念,第10页,一、图的基本概念,现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。 例：A、B、C、D四个队举行篮球比赛，为了表示个队之间比赛的情况， 我们作出下图。 在图中个小圆圈分别

4、表示这个篮球队， 称之为结点。 如果两队进行过比赛， 则在表示该队的两个结点之间用一条线连接起来， 称之为边。 这样利用一个图形使各队之间的比赛情况一目了然。,A,B,D,C,第11页,一、图的基本概念,定义7-1.1 图的定义： 一个图G是一个二元组，其中 V(G) =v1,v2, ,vn，是一个有限非空集合， vi称为结点，V(G)称为结点集合，简记为V。 E(G(=e1,e2,em，是一个有限集合，ei称为边，ei用结点的偶对表示，E(G)称为边集合，简记为E。,第12页,二、关于图的一些术语,若边e与无序结点对 (vi,vj)对应，则称e为无向边，vi，vj为ek的端点。 若边e与有序

5、结点对 对应，则称e为有向边，vi称作e的起始结点，vj称作e的终止结点，但统称为e的端点。 ek与vi或ek与vj是彼此相关联的。 邻接点：关联于同一边的结点称为邻接点。 邻接边：关联于同一结点的边称为邻接边。 关联于同一结点的边称为环或自回路。 注意：环的方向没有意义，可以看作无向边也可看作有向边 无论在无向图中还是在有向图中，无边关联的结点均称孤立点。,第13页,三、 图的表示,对于一个图G，如果将其记为G = ，并写出V和E的集合表示，这称为图的集合表示。 而为了描述简便起见，在一般情况下，往往只画出它的图形：用小圆圈表示V中的结点，用由u指向v的有向线段或曲线表示有向边，无向线段或曲

6、线表示无向边(u, v)，这称为图的图形表示。,第14页,例7-1.1,设图G = ，这里V = v1, v2, v3, v4, v5，E = e1, e2, e3, e4, e5, e6，其中e1 = (v1, v2)，e2 = ，e3 = (v1, v4)，e4 = (v2, v3)，e5 = ，e6 = (v3, v3)。试画出图G的图形，并指出哪些是有向边，哪些是无向边？ 解：G的图形如下图所示。,G中的e1、e3、e4、e6是无向边，e2、e5是有向边。,第15页,例7-1.2,设图G = 的图形如下图所示，试写出G的集合表示。,1,2,3,4,5,解 图G的集合表示为G = = ，

7、 (1, 4)，(1, 5)，(2, 3)， 。,第16页,两种描述方法的优缺点,用集合描述图的优点是精确，但抽象不易理解； 用图形表示图的优点是形象直观，但当图中的结点和边的数目较大时，使用这种方法是很不方便的，甚至是不可能的。,第17页,四、图的分类,边方向,平行边,第18页,每一条边都是无向边的图称作无向图。 每一条边都是有向边的图称作有向图。 若图中既有无向边也有有向边，称为混合图。 例7-1.3：判断下面图是无向图、有向图或混合图 分析：判断无向图、有向图和混合图，仅看边有无方向。,有向图,无向图,混合图,第19页,定义7-1.2 含有平行边的图称为多重图。 不允许有环和平行边的图称

8、为简单图 。 注意：不是多重图，不一定是简单图。,连接于同一对结点间的多条边称为是平行边。,多重图,简单图,非多重图，非简单图,第20页,没有任何边的图称为零图； 只有一个点的图称为平凡图； 含有n个结点，m条边的图，称为(n,m)图。,(a) 4阶零图 N4,(b) 平凡图,特殊图,V1,V2,V3,(c) (3,5)图,第21页,五、完全图,定义7-1.4 设G为n阶无向简单图，若G中每个结点均与其余的n-1个结点相邻，则称G为n阶无向完全图，简称n阶完全图，记做Kn(n1)。 设D为n阶有向简单图，若D中每个结点都邻接到其余的n-1个结点，又邻接于其余的n-1个结点，则称D是n阶有向完全

9、图。 设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。 基图：将有向图各有向边去掉方向后的无向图称为原来图的基图。,第22页,例7-1.4 下图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的无向完全图。,完全图例,第23页,定理7-1.1 n阶无向完全图，n阶有向完全图，n阶有向竞赛图的边数分别为 n(n-1)/2，n(n-1) ， n(n-1)/2,完全图边数,第24页,六、子图、母图、生成子图、补图,定义7-1.5 设G，H是图，若G，H满足 (1)若V(H)V(G)，E(H)E(G), 则称H是G的子图，G是H的母图。 (2)若H是G的子图，并且V

10、(H)V(G)， 则称H是G的生成子图。,（a)母图,(c)生成子图,(b) 子图,注意，孤立结点一定不要漏了，否则结点集就不同。,第25页,v3,v2,v4,v1,v5,v6,删除v1,删除边(v4,v6),(1)删除结点v，是将v以及与v关联的边都删去。 (2)删除边e，是仅将边e删去。,删除图中的点、边,第26页,注意，孤立结点一定不要漏了，否则结点集就不同。,补图,(a)原图,(b)补图,定义7-1.6 图G相对于完全图的补图：设G为具有n个结点的图，从完全图Kn中删去G中的所有边而得到的图，称为G的补图，表示为 。 例7-1.5，求图(a)的补图,第27页,定义7-1.7 设G=是图

11、G=的子图，从G中删去G的边，且删去孤立结点后得到的图G(即G中仅包含G的边所关联的结点），则称G是子图G的相对于图G的补图。 例7-1.6：,子图相对于母图的补图,母图,a,b,c,d,a1,b1,子图,注意，孤立结点一定要删掉。,第28页,七、结点的度数,定义7-1.8：在图G=， viE，与vi关联的边的条数称为该结点的度数，记为deg(vi)。 （约定：每个环在其对应结点度数上增加2） 图G最大度数记为(G)，最小度数记为(G)。 定义7-1.9：在有向图G=中，vV, 以v为起始结点的边的条数称为该点的出度，记作deg+(v); 以v为终止结点的边的条数称为该点的入度，记作deg-(

12、v)。 每个环在其对应结点的出度增加1，给入度增加1. 显然有deg(v)=deg+(v)+deg-(v),第29页,求出下图的最大度和最小度，求出图中每个结点的出，入度。,v1,v2,v3,v4,= 12,(G)=5，(G)=2,例7-1.7,第30页,度数列 设V=v1,v2,v3, ,vn是图G的结点集，称 (deg(v1), deg(v2), deg(v3), , deg(vn)为G的度数列。,度数列为：(4,4,2,1,3),= 14,第31页,握手定理,定理7-1.2 设G=为任意图(无向的或有向的) ，V=v1,v2,vn，|E|=m，则,所有结点的度数之和=边数的两倍,证明：

13、G中每条边(包括环)均有两个端点，所以在计算G中各结点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。,= 2|E|= 2m,第32页,这个结果是图论的第一个定理，它是由欧拉于1736年最先给出的。欧拉曾对此定理给出了这样一个形象论断：如果许多人在见面时握了手，两只手握在一起，被握过手的总次数为偶数。故此定理称为图论的基本定理或握手定理。,今后常称度数为奇数的结点为奇度数结点(Odd Degree Point)，度数为偶数的结点为偶度数结点(Even Degree Point)。,第33页,握手定理的推论,定理7-1.3 任何图(无向的或有向的)中，奇度数结点的个数是偶数。 证明：

14、设G=为任意一图，令 V1是偶度数结点的集合， V2是奇度数结点的集合， V1V2=V，V1V2= ， 由握手定理可知,由于2m， 均为偶数，所以 为偶数，但因V2中deg(v)为奇数，所以V2中元素的个数必为偶数，即奇度数结点的个数是偶数。,2m= = +,第34页,握手定理的推论,定理7-1.4 任何有向图中，所有结点的入度之和等于所有结点的出度之和。 证明： 因为每一条边必给结点的入度之和增加1，给结点的出度之和增加1，所以，有向图中所有结点的入度之和等于边数，所有结点的出度之和等于边数。因此，所有结点的入度之和等于所有结点的出度之和。,第35页,握手定理的应用,V=v1, v2, ,

15、vn为无向图G的结点集，称deg(v1), deg(v2), , deg(vn)为G的度数列。 下面整数列是否可图化？ (1) (5, 3, 3, 2, 1); (2) (2, 2, 3, 1, 5)。 解： (1) deg(i) = 偶数， 所以(1)可图化，或奇数度结点为偶数，则其图化解可有多个。 (2) 中有3个奇度结点, 由握手定理, 图G中奇度结点必为偶数个, 所以(2)不可图化。 下面整数列是否可简单图化？ (2, 3, 2, 4, 6, 5); 解:是阶为6的简单图, (G)5, 所以不可简单图化。,第36页,握手定理的应用,练习题1：设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3求G中有多少个结点。 解：设图G有x个结点，有握手定理 21+22+34+3(x-2-2-3)122 x9 图G有9个结点。,第37页,证明： 方法一：穷举法 设G有x个5度结点， 则G有9-x个6度结点，由握手定理推论可知： x只能取 0，2，4，6，8； 9-x只能取9，7，5，3，1。 于是(x,9-x)为(0,9)