离散数学及其应用课件第8章特殊图

1、离散数学及其应用第8章 特殊图8.1 欧拉图与哈密顿图8.2 带权图8.3 匹配和二分图8.4 平面图8.1 欧拉图与哈密顿图哥尼斯堡七桥问题、周游世界问题欧拉图定义8.1.1 设G=（V，E）是无向图或有向图，若G中有一条包含所有边（有向边）的简单回路，称该回路为欧拉回路，称图G为欧拉图。若G中有一条包含G中所有边（有向边）的简单通路，称它为欧拉通路，称图G为半欧拉图。 欧拉图 半欧拉图例题b-c-d-b-e-c-a-b b-d-c-e-b-a-c 例8.1.1 在下面的图中，哪些有欧拉回路？没有欧拉回路的图中，哪些有欧拉通路？欧拉图的判断 定理8.1.1 无向连通图G是欧拉图，当且仅当G的

2、所有结点的度数都是偶数。定理8.1.2 连通无向图G为半欧拉图，当且仅当G中只有两个奇度数的结点。定理8.1.1证明定理8.1.1 无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶数。证明：（必要性）设G是欧拉图，则G有欧拉回路C。设a是图G的任一结点，欧拉回路经过和a关联的边到结点a后又经过另一条和a关联的边离开到下一个结点b，因此每经过一个结点a就给它的度数贡献2度。若欧拉回路k次经过结点a，则d（a）=2k。所以，欧拉图的所有结点的度数都是偶数。（充分性）假设G中所有结点的度数都是偶数。从G中的任一结点v1开始，经过任一和v1关联的边e1到另一结点v2，再经过另一和v2关联的边e2

3、到另一结点v3，依此类推，可以得到一条包含G的边的简单回路C1：v1 e1 v2 e2 v3 em v1。定理8.1.2证明定理8.1.2 连通无向图G为半欧拉图，当且仅当G中只有两个奇度数的结点。证明 在连通无向图G的两个奇度数的结点之间加一条边e得到图G，则图G的所有结点的度数都是偶数，有欧拉回路。在G的欧拉回路中删去这条边e，则可得到一条包含G中所有边的欧拉通路。因此图G是半欧拉图。例题例8.1.2 在下图中，哪些是欧拉图？哪些是半欧拉图？ 欧拉图 欧拉图 半欧拉图欧拉有向图定义8.1.2 如果连通有向图G中有一条包含G中所有有向边的有向回路，称它为欧拉有向回路，称图G为欧拉有向图。如果

4、连通有向图G中有一条包含G中所有有向边的有向通路，称它为欧拉有向通路，称图G为半欧拉有向图。欧拉有向图 半欧拉有向图欧拉有向图的判断 定理8.1.3 连通有向图G是欧拉图，当且仅当G中每个结点v的入度等于它的出度。定理8.1.4 连通有向图G是半欧拉图，当且仅当G中有且仅有两个奇度数结点，其中一个结点的入度比出度大1，另一个结点的入度比出度小1。例题例8.1.3 在图中，哪些是欧拉图？哪些是半欧拉图？欧拉图 半欧拉图8.1.2 哈密顿图环游世界问题哈密顿图定义8.1.3 设图G=（V，E）是无向图或有向图。若G中有一条包含G的所有结点(仅一次)的回路，称该回路为哈密顿回路，称图G为哈密顿图。若

5、图G有一条包含G的所有结点的通路，称该通路为哈密顿通路，称图G为半哈密顿图。(1)是半哈密尔顿图 (2)为哈密尔顿图 (3)没有哈密顿通路，也没有哈 密顿回路哈密顿图的必要条件定理8.1.5 设无向图G=（V，E）是哈密顿图，则对于结点集V的每一个真子集S均有：W(G-S)|S|, 其中，W(G-S)是G-S的导出子图的连通分支数。例如：彼德森图中对于结点集V的每一个真子集S均有：W(G-S)|S|。但彼德森图不是哈密顿图。例题例8.1.4 说明下图 所示的无向图G不是哈密顿图。解 在图中删去结点集S=v2，v4，v6，v8，W(GS)=5，不满足W(G-S)|S|。所以G不是哈密顿图。哈密顿

6、图的充分条件定理8.1.6 如果G是有 n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v) n-1，那么G中存在哈密顿通路，图G是半哈密顿图。推论1 如果图G是有 n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u) + d(v) n，那么G中存在哈密顿回路，图G是哈密顿图。推论2 如果G是有 n个结点的简单无向图，G中每个结点的度数都至少为n/2，那么图G是哈密顿图。例题应用1例8.1.5 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否

7、将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈?图G的一条哈密顿回路是ABDFGECA，按这条哈密顿回路安排就坐成一圈, 每个人都能与两旁的人交谈。应用2-格雷码例8.1.6 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。表8.1.1是2位格雷码，表示数03，表8.1.2是3位格雷码，表示数07。格雷码用格雷码表示的最大数与最小数之间也仅一位数不同，即“首尾相连”，因此这种编码又称循环码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同

8、时发生，则计数中可能出现短暂的其它代码（如0110、1111等）。在特定情况下可能导致电路状态错误或输入输出错误。使用格雷码，变化到下一状态时只有1位不同，可以避免这种错误。格雷码要找到格雷码，可以用n立方体Qn来建模。在Qn图上找一条哈密顿回路，按哈密顿回路上的结点顺序对应的二进制码序列就是格雷码。例如，8.2 带权图设G=，V=v1，v2，vn是顶点集合，E是边集合，W: VVR是赋值函数。旅行商问题(TSP)完全无向图的每个结点表示一个城市，用两个城市之间的距离作为边的权，可以得到一个边带权的完全无向图。旅行商问题是在这样的图中寻找一条旅行总距离最短的经过每个城市一次且仅一次，又回到出发

9、城市的旅行线路的问题。这个问题等价于求带权完全图中总权值最小的哈密顿回路。8.2.1 旅行商问题 n个结点的图上，以每个结点为起点的所有的哈密顿回路共有(n-1)! 条，需要计算(n-1)!/2条回路的权值来求出答案。当结点较多时用这种方法解决旅行商问题是不切实际的，常用近似算法求解旅行商问题。8.2.2最短路径问题在一个无向简单连通边带权图G=（V，E，W）中，从u到v的一条通路中包含的各条边的权值之和称为这条通路的长度。从u到v的所有通路中长度最短的通路称为u到v的最短路径。求给定两结点之间的最短路径问题称为最短路径问题uadv是u到v的最短路径Dijkstra算法1. 初始化。除L(u)

10、初始化为0，其它所有顶点L(vi)=+，i=1,2,n. S=u。2. 修改和结点u相邻的结点的标记值：L(vi)= W(u,vi)。3. 将具有最小L值的结点记为t，并添加到结点集S中，即S = St。4. 修改和结点t相邻且不在集合S中的结点的L值：L(vi)=minL(vi), L(t)+W(t,vi)。5. 重复3和4直到结点v被添加到集合S中。Dijkstra算法8.2.3 中国邮路问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他负责范围内的每一条街道，如何选择投递路线，邮递员可以走尽可能少的路程？这个问题是由我国数学家管梅

11、谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮路问题用图论的述语，在一个连通的带权图G=（V，E，W）中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的总权值最小，也就是说要从包含G的每条边的回路中找一条总权值最小的回路。中国邮路问题如果G是欧拉图，只要求出图G的一条欧拉回路即可。因此问题就转化为：在有奇度数结点的连通带权图中，在包含G中每条边至少一次的回路中找一条总权值最小的回路。中国邮路问题首先注意到，若图G有奇数度结点，则G的奇数度结点必是偶数个把奇数度结点配为若干对，每对结点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子

12、集E1令G1 =G+E1，即把附加边子集E1 叠加在原图G上形成一个多重图G1，这时G1中没有奇度数结点显然G1是一个欧拉图，因而可以求出G1的欧拉回路该欧拉回路不仅通过原图G中每条边，同时还通过E1 中的每条边，且均仅一次邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E1 的权数W(E1)为最小。定理 8.2.1 设G（V，E，W）为一个连通的带权图，则使附加边子集E1 的权数W(E1)为最小的充分必要条件是G+E1 中任意边至多重复一次，且G+E1 中的任意回路中重复边的权值之和不大于该回路总权值的一半。中国邮路问题8.3 匹配和二分

13、图定义8.3.1 在图G=(V，E)中, 若ME, 且M中任意两条边都不相邻，则称M为G的一个匹配。若在M中再加入任意其它的边e，Me有相邻的边，则称M为G的极大匹配。若G中不存在匹配M1，使得|M1| | M|，则称M为G的最大匹配。定义8.3.2若M是G的一个匹配，M的边和结点v关联，则称v为M饱和点，否则称v为M非饱和点。若G=（V，E）的每个结点都是M饱和点，则称M为G的一个完美匹配。例题(1). e1, e7是图的一个匹配，也是一个极大匹配， e2, e4, e8是图的最大匹配，也是完美匹配。(2). e2, e6、e3, e5是图的匹配，也是极大匹配， e1, e4, e7是图的一

14、个最大匹配，也是完美匹配。(3).e3, e4、e1, e5、e2, e6、e4, e7等都是极大匹配，也是最大匹配，没有完美匹配。M交错路和M可扩充路定义8.3.3 若M是G=（V，E）的一个匹配，从G中的一个结点到另一个结点存在一条由属于M的边和不属于M的边交替出现组成的简单路，则称这条简单路为M交错路。若M交错路的两端点为M非饱和点时，称这条M交错路是M可扩充路。最大匹配的充分必要条件在图（1）中，M=e1，e7是图的一个匹配， e2, e1, e4, e7, e8是M交错路，而且是M可扩充路。匹配M1= e2, e4, e8比M更大。 定理8.3.1 M是图G=(V，E)的最大匹配的充

15、分必要条件是G中不存在M可扩充路。例题求右图的最大匹配。解 在图中，M=（v2，v6），（v3，v5），（v4，v7） 是匹配，v1v5v3v6v2v7v4v8是M交错路，而且是M可扩充路。因此，存在比M更大的匹配M1=（v1，v5），（v3，v6），（v2，v7），（v4，v8） 。由于不存在M1可扩充路，所以M1是最大匹配。8.3.2 二分图定义8.3.4 如果无（有）向图G=（V，E）的结点集V能划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二分（部）图，V1和V2称为互补结点集，二分图通常记为G=（V1，V2，E）。若V1中每一结点与V2中

16、每一个结点均有且仅有一条边相关联，则称二分图G为完全二分图。若| V1|=m ， | V2|=n ，则记完全二分图G为Km，n。二分图例如，一个单位有一些不同类型的工作空缺，有一些应聘者申请这些空缺的工作岗位。每个应聘者能胜任这些工作中的某些工作。如工作岗位集合为u1，u2，u3，应聘者集合为v1，v2，v3，v4，v5。每个应聘者能胜任的工作岗位可以图8.3.3所示的二分图表示，其中线uivj表示工作岗位ui适合应聘者vj。二分图完全二分图二分图的判断定理8.3.2 一个无向简单图G=（V，E）是二分图，当且仅当G中无奇数长度的回路。 证明 (必要性)设无向简单图G=（V，E）是二分图，V1

17、V2=V，V1V2=。对于G中任一长度为n的回路可表示为v1e1v2e2vnenv1。设v1V1，则v2V2，v3V1，v4V2 vnV2。所以n必为偶数。（充分性）设无向简单图G=（V，E）的所有回路的长度都是偶数。u是图G的任一结点，d（v，u）表示结点v到结点u的距离。二分图的结点集V的两个子集可以表示为：V1=v| d(v, u)为偶数，V2=V-V1。如果存在一条边e的两端点vi和vj都在结点集V1中，则从vi到vj存在一条有偶数条边的通路L。通路L和边e可以构成一条回路，回路的长度为奇数。和假设矛盾。同理可证，没有一条边的两端点都在结点集V2中。由此可见，图G的每条边的端点，必定一

18、个在结点集V1中，另一个在结点集V2中，而且V1和V2是G的互补结点集。所以图G是二分图。例题判断图8.3.6中的图是否是二分图。完全匹配和完美匹配定义8.3.5 设G=（V，E）是二分图，V1和V2是G的互补结点集，若G的一个匹配M使得|M|=min| V1|，| V2|，称匹配M是G的完全匹配。这时，若| V1| V2|，称M是从V1到V2的一个完全匹配。如果| V1|=| V2|，称M是G的完美匹配。完全匹配完美匹配没有完全匹配完全匹配定理8.3.3（Hall定理） 设二分图G = (V,E )，V1和V2 是G的互补结点集，存在从V1到V2的完全匹配, 当且仅当对于V1中的任意k个结点

19、（k=1,2, ,|V1|）至少邻接V2的k个结点。 定理8.3.3中的条件通常称为相异性条件。定理8.3.4 设G=（V，E）是二分图，V1和V2 是G的互补结点集。若存在正整数t，使V1中的每个结点至少关联t条边；V2中的每个结点至多关联t条边，则G中存在从V1到V2的完全匹配。定理定理8.3.4 设G=（V，E）是二分图，V1和V2 是G的互补结点集。若存在正整数t，使V1中的每个结点至少关联t条边；V2中的每个结点至多关联t条边，则G中存在从V1到V2的完全匹配。证明 由条件（1）可知，V1中的k个结点至少关联kt条边（1k|V1|）。由条件（2）可知，这些边至少关联V2中的k个结点。

20、因此，V1中的k个结点至少邻接V2中的k个结点。由Hall定理,G中存在完全匹配。例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应如何排课才可以使每天都只有一位教师上课？例题M=（A，p2），（B，p3），（C，p4），（D，p5），（E，p1）8.4 平面图定义8.4.1 设G=（V，E）是一个无向图，如果能把G画在平面上，使得除结点处外，任意两条边都不相交，则称G为平面图。将一个平面图G，画成除结点处外，任意两条边都不相交的和它同构的图，称这样的图为图G

21、的平面嵌入。例题判断图8.4.1中的各图是否是平面图。 （1） （2） （3） （4）解 （1）（2）（4）不是平面图，而(3) 是平面图。 平面图定义8.4.2 设G是一个平面嵌入，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面。其中，面积无限的区域称为无限面或外部面，记成f0，面积有限的区域称为有限面或内部面，记为f1，f2，fk 。包围每个面的所有边所构成的回路称为该面的边界。一个面的边界包含的边数称为该面的次数，记为deg(f)。平面图面f0的边界回路是一个复杂回路，Deg(f0)=9，面f1的边界回路是环，Deg(f1)=1，面f2和f3的边界回路是简单回路，Deg(f

22、2)=3，Deg(f3)=3定理定理8.4.1 一个连通平面图G的边数为e，G的边将G所在的平面划分成l个面，所有面的次数之和等于边数e的2倍，即 证明 对图G的每一条边e，若e在两个面的公共边界上，则在计算这两个面的次数时，e各提供1.当e只在一个面的边界上出现时，它必在一个面的边界上出现2次，如图 所示，因而在计算这个面的次数时，e提供2.因此所有面的度数之和等于边数e的2倍。欧拉公式定理8.4.2 设G为任意的连通的平面图，G中有n个结点，e条边，f个面，则有公式n-e+f=2 成立。该公式称为欧拉公式。证明 对边数e用归纳法。 例8.4.2 假定连通平面图G有30条边，若G的边把图分成

23、20个区域，则这个图有多少个结点？解 根据题意，连通平面图G的边数e=30，面数f=20，代入欧拉公式n-e+f=2得：n=2+e-f=2+30-20=12所以这个图有12个结点。欧拉公式的推论推论1 设G是有n （n 3）个结点，e条边，f个面的简单连通平面图，边数e 3n-6。证明 当n=3，3个结点的简单连通平面图的边数e3f/2, 因此e 3n-6成立。当n 3时，G的每个面至少由3条边围成，即每个面的度数deg(fi)3, 所以所有面的总度数deg(fi)3f。而deg(fi)=2e , 因而有2e 3f, 即f 2e/3。代入欧拉公式 2= n-e+f n-e+2e/3 有 e 3

24、n-6成立。因此e 3n-6成立。欧拉公式的推论推论2 设G是有n（n 3）个结点，e条边，f个面的简单连通平面图，若每个面由4条或4条以上的边围成, 则e 2n- 4。推论3 K5和K3，3都不是平面图。定理定理8.4.3 设G是有n个结点，e条边的简单连通平面图，则G中至少存在一个结点v，使得d（v） 5。证明 假设G中每个结点v，都有d（v） 6，则由握手定理有6nd（v）=2e即有e 3n3n-6，与推论1矛盾。欧拉公式的推广定理8.4.4 （欧拉公式的推广）设G为任意的平面图，G有k个连通分支，n个结点，e条边，f个面，则有公式n-e+f=k+1成立。插入和删去结点、同胚定义8.4.

25、3 设e=（u，v）是图G的一条边，在G中删去边e，增加新的结点w，使u，v均与w相邻，则称在图G中插入2度结点w；设w为G的一个度数为2的结点，w与u，v相邻，删去w及与w相关联的边(w，u)，(w，v)，同时增加新边(u，v)，则称在图G中删去2度结点w。定义8.4.4 若两个图G1和G2同构或通过反复插入或删除2度结点后是同构的，则称G1和G2是同胚的。平面图的充分必要条件定理8.4.5（ 库拉托斯基定理） 设G是无向图，则G是平面图的充分必要条件是图G不含和K5或K3，3同胚的子图。推论 设G是无向图，则G是平面图的充分必要条件是图G没有可收缩为K5或K3，的子图。例题彼得森图中删去边（7,8）和（4,5）的子图， 和K3，3同胚。所以彼得森图不是平面图。8.4.3 对偶图与着色定义8.4.5 设G是平面图。在图G的每个面中指定一个新结点，对两个面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图称为G的对偶图G*。给定平面图G，用如下的方法构造G的对偶图G*：在G的每一个面fi中任取一个结点vi*作为G*的结点；若ek是G的两个面fi和fj的公共边，有一条边ek*=（vi*，vj*）作为G*的边，且（vi*，vj*）与ek相交；若ek只是G的一个面fi的边界时，以fi中的结点vi*为结点做环ek