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
2、.1.1 无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶数。定理定理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关联
3、的边e1到另一结点v2，再经过另一和v2关联的边e2到另一结点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中有一条
4、包含G中所有有向边的有向回路，称它为欧拉有向回路，称图G为欧拉有向图欧拉有向图。如果连通有向图G中有一条包含G中所有有向边的有向通路，称它为欧拉有向通路，称图G为半欧拉有向图半欧拉有向图。abcdabcdabcd欧拉有向图 半欧拉有向图欧拉有向图的判断 定理定理8.1.3 连通有向图G是欧拉图，当且仅当G中每个结点v的入度等于它的出度。定理定理8.1.4 连通有向图G是半欧拉图，当且仅当G中有且仅有两个奇度数结点，其中一个结点的入度比出度大1，另一个结点的入度比出度小1。例题例例8.1.3 在图中，哪些是欧拉图？哪些是半欧拉图？欧拉图 半欧拉图8.1.2 哈密顿图环游世界问题哈密顿图定义定义8
5、.1.3 设图G=（V，E）是无向图或有向图。若G中有一条包含G的所有结点(仅一次)的回路，称该回路为哈密顿回路哈密顿回路，称图G为哈密顿图哈密顿图。若图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|。但彼德森图不是哈密顿图
6、。286753417684325910178634例题例例8.1.4 说明下图 所示的无向图G不是哈密顿图。解解 在图中删去结点集S=v2，v4，v6，v8，W(GS)=5，不满足W(G-S)|S|。所以G不是哈密顿图。哈密顿图的充分条件定理定理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中每个结点的度数都
7、至少为n/2，那么图G是哈密顿图。例题应用1例例8.1.5 有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?图G的一条哈密顿回路是ABDFGECA，按这条哈密顿回路安排就坐成一圈,每个人都能与两旁的人交谈。应用2-格雷码例例8.1.6 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码格雷码。表8.1.1是2位格雷码，表示数03，表8.1.2是3位格雷码，表示数07。格雷码用格雷码表示的最大数与最小数
8、之间也仅一位数不同，即“首尾相连”，因此这种编码又称循环码循环码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（如0110、1111等）。在特定情况下可能导致电路状态错误或输入输出错误。使用格雷码，变化到下一状态时只有1位不同，可以避免这种错误。格雷码要找到格雷码，可以用n立方体Qn来建模。在Qn图上找一条哈密顿回路，按哈密顿回路上的结点顺序对应的二进制码序列就是格雷码。例如，8.2 带权图设G=，V=v1，v2，vn是顶点集合，E是边集合，
9、W:VVR是赋值函数。旅行商问题旅行商问题(TSP)完全无向图的每个结点表示一个城市，用两个城市之间的距离作为边的权，可以得到一个边带权的完全无向图。旅行商问题是在这样的图中寻找一条旅行总距离最短的经过每个城市一次且仅一次，又回到出发城市的旅行线路的问题。这个问题等价于求带权完全图中总权值最小的哈密顿回路。8.2.1 旅行商问题 n个结点的图上，以每个结点为起点的所有的哈密顿回路共有(n-1)!条，需要计算(n-1)!/2条回路的权值来求出答案。当结点较多时用这种方法解决旅行商问题是不切实际的，常用近似算法求解旅行商问题。8.2.2最短路径问题 在一个无向简单连通边带权图G=（V，E，W）中，
10、从u到v的一条通路中包含的各条边的权值之和称为这条通路的长长度。度。从u到v的所有通路中长度最短的通路称为u到v的最短路径最短路径。求给定两结点之间的最短路径问题称为最短路径问题uadv是u到v的最短路径Dijkstra算法1.初始化。除L(u)初始化为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
11、算法8.2.3 中国邮路问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他负责范围内的每一条街道，如何选择投递路线，邮递员可以走尽可能少的路程？这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮路问题 用图论的述语，在一个连通的带权图G=（V，E，W）中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的总权值最小，也就是说要从包含G的每条边的回路中找一条总权值最小的回路。中国邮路问题如果G是欧拉图，只要求出图G的一条欧拉回路即可。因此问题就转化为：在有奇度数结点的连通
12、带权图中，在包含G中每条边至少一次的回路中找一条总权值最小的回路。中国邮路问题首先注意到，若图G有奇数度结点，则G的奇数度结点必是偶数个把奇数度结点配为若干对，每对结点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E1令G1=G+E1，即把附加边子集E1 叠加在原图G上形成一个多重图G1，这时G1中没有奇度数结点显然G1是一个欧拉图，因而可以求出G1的欧拉回路该欧拉回路不仅通过原图G中每条边，同时还通过E1 中的每条边，且均仅一次邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E1 的权数W(E1)为最小。定理定理 8.
13、2.1 设G（V，E，W）为一个连通的带权图，则使附加边子集E1 的权数W(E1)为最小的充分必要条件是G+E1 中任意边至多重复一次，且G+E1 中的任意回路中重复边的权值之和不大于该回路总权值的一半。中国邮路问题8.3 匹配和二分图定义定义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
14、=（V，E）的每个结点都是M饱和点，则称M为G的一个完美匹配完美匹配。例题(1).e1,e7是图的一个匹配，也是一个极大匹配，e2,e4,e8是图的最大匹配，也是完美匹配。(2).e2,e6、e3,e5是图的匹配，也是极大匹配，e1,e4,e7是图的一个最大匹配，也是完美匹配。(3).e3,e4、e1,e5、e2,e6、e4,e7等都是极大匹配，也是最大匹配，没有完美匹配。M交错路和M可扩充路可扩充路定义定义8.3.3 若M是G=（V，E）的一个匹配，从G中的一个结点到另一个结点存在一条由属于M的边和不属于M的边交替出现组成的简单路，则称这条简单路为M交错路交错路。若M交错路的两端点为M非饱和
15、点时，称这条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)的最大匹配的充分必要条件是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 二分
16、图定义定义8.3.4 如果无（有）向图G=（V，E）的结点集V能划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二分（部）图二分（部）图，V1和V2称为互补互补结点集结点集，二分图通常记为G=（V1，V2，E）。若V1中每一结点与V2中每一个结点均有且仅有一条边相关联，则称二分图G为完全二分图完全二分图。若|V1|=m，|V2|=n，则记完全二分图G为Km，n。二分图例如，一个单位有一些不同类型的工作空缺，有一些应聘者申请这些空缺的工作岗位。每个应聘者能胜任这些工作中的某些工作。如工作岗位集合为u1，u2，u3，应聘者集合为v1，v2，v3，v4，v
17、5。每个应聘者能胜任的工作岗位可以图8.3.3所示的二分图表示，其中线uivj表示工作岗位ui适合应聘者vj。二分图完全二分图二分图的判断定理定理8.3.2 一个无向简单图G=（V，E）是二分图，当且仅当G中无奇数长度的回路。证明证明 (必要性)设无向简单图G=（V，E）是二分图，V1V2=V，V1V2=。对于G中任一长度为n的回路可表示为v1e1v2e2vnenv1。设v1V1，则v2V2，v3V1，v4V2 vnV2。所以n必为偶数。（充分性）设无向简单图G=（V，E）的所有回路的长度都是偶数。u是图G的任一结点，d（v，u）表示结点v到结点u的距离。二分图的结点集V的两个子集可以表示为：
18、V1=v|d(v,u)为偶数，V2=V-V1。如果存在一条边e的两端点vi和vj都在结点集V1中，则从vi到vj存在一条有偶数条边的通路L。通路L和边e可以构成一条回路，回路的长度为奇数。和假设矛盾。同理可证，没有一条边的两端点都在结点集V2中。由此可见，图G的每条边的端点，必定一个在结点集V1中，另一个在结点集V2中，而且V1和V2是G的互补结点集。所以图G是二分图。例题判断图8.3.6中的图是否是二分图。ecdababcdeabcdfe完全匹配和完美匹配定义定义8.3.5 设G=（V，E）是二分图，V1和V2是G的互补结点集，若G的一个匹配M使得|M|=min|V1|，|V2|，称匹配M是
19、G的完全匹配完全匹配。这时，若|V1|V2|，称M是从V1到V2的一个完全匹配。如果|V1|=|V2|，称M是G的完美匹配完美匹配。完全匹配完美匹配没有完全匹配完全匹配定理定理8.3.3（Hall定理）定理）设二分图G=(V,E)，V1和V2 是G的互补结点集，存在从V1到V2的完全匹配,当且仅当对于V1中的任意k个结点（k=1,2,|V1|）至少邻接V2的k个结点。定理8.3.3中的条件通常称为相异性条件相异性条件。定理定理8.3.4 设G=（V，E）是二分图，V1和V2 是G的互补结点集。若存在正整数t，使1.V1中的每个结点至少关联t条边；2.V2中的每个结点至多关联t条边，则G中存在从
20、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个结点。因此，V1中的k个结点至少邻接V2中的k个结点。由Hall定理,G中存在完全匹配。例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星期五，D的时间是星期二和星期五，E的时间是星
21、期一和星期四。应如何排课才可以使每天都只有一位教师上课？例题M=（A，p2），（B，p3），（C，p4），（D，p5），（E，p1）8.4 8.4 平面图平面图定义定义8.4.1 设G=（V，E）是一个无向图，如果能把G画在平面上，使得除结点处外，任意两条边都不相交，则称G为平平面图面图。将一个平面图G，画成除结点处外，任意两条边都不相交的和它同构的图，称这样的图为图G的平面嵌入平面嵌入。例题判断图8.4.1中的各图是否是平面图。（1）（2）（3）（4）解解 （1）（2）（4）不是平面图，而(3)是平面图。平面图定义定义8.4.2 设G是一个平面嵌入，G的边将G所在的平面划分成若干个区域，每个
22、区域称为G的一个面面。其中，面积无限的区域称为无限面无限面或外部面外部面，记成f0，面积有限的区域称为有限有限面面或内部面内部面，记为f1，f2，fk。包围每个面的所有边所构成的回路称为该面的边界面的边界。一个面的边界包含的边数称为该面的次面的次数数，记为deg(f)。平面图面f0的边界回路是一个复杂回路，Deg(f0)=9，面f1的边界回路是环，Deg(f1)=1，面f2和f3的边界回路是简单回路，Deg(f2)=3，Deg(f3)=3f1f0f2f3v1v2v3v4v5v6定理定理定理8.4.1 一个连通平面图G的边数为e，G的边将G所在的平面划分成l个面，所有面的次数之和等于边数e的2倍
23、，即 证明证明 对图G的每一条边e，若e在两个面的公共边界上，则在计算这两个面的次数时，e各提供1.当e只在一个面的边界上出现时，它必在一个面的边界上出现2次，如图 所示，因而在计算这个面的次数时，e提供2.因此所有面的度数之和等于边数e的2倍。eflii2)deg(0欧拉公式定理定理8.4.2 设G为任意的连通的平面图，G中有n个结点，e条边，f个面，则有公式n-e+f=2 成立。该公式称为欧拉公式欧拉公式。证明证明 对边数e用归纳法。例例8.4.2 假定连通平面图G有30条边，若G的边把图分成20个区域，则这个图有多少个结点？解解 根据题意，连通平面图G的边数e=30，面数f=20，代入欧
24、拉公式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 3n-6成立。因此e 3n-6成立。欧拉公式的推论推论推论2 设G是有n（n 3）个结点，e条边，f个面
25、的简单连通平面图，若每个面由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.3 设e=（u，v）是图G的一条边，在G中删去边e，增加新的结点w，使u，v均与w相邻，
26、则称在图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同胚。所以彼得森
27、图不是平面图。12637891045126378910458.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*，ek*与ek相交，ek*是G*的一个环。对偶图设n、e、f分别为平面图
28、G的结点数、边数和面数，n*、e*、f*分别为G的对偶图G*的结点数、边数和面数，按照对偶图的定义有n*=f,e*=e,f*=n。着色定义定义8.4.6 对一个简单图G进行着色着色,是指给它的每个结点指定一种颜色，使得相邻结点都有不同的颜色。若用了k种颜色给G的结点着色，则称G是k-可着色的。定义定义8.4.7 给图G的结点着色所用的最少的颜色数，称为图G的色数色数。最少用了k种颜色，则称G是k色图色图。定理定理定理8.4.6 对于任意的无环图G，G的色数为k，则k(G)+1，(G)是G的结点最大度数。定理定理8.4.7（Brooks定理）定理）对于无环图G，G的色数为k，若G不是完全图，也不
29、是长度为奇数的基本回路，则k(G)。二分图Km,n图的色数是多少?四色定理定理定理8.4.8(四色定理四色定理)对一个平面图的各个面进行着色,使得相邻的面有不同的颜色,那么所用的颜色可以不多于4色。定义定义8.4.8 对于无环图G的每条边指定一种颜色，使得相邻的边有不同的颜色，称为对图G的边着色。若能用k种颜色给G的边着色，则称G是k-可边着色的。若对G的边着色用的最少颜色数为k，则称G的边色数为k.定理定理8.4.9 设G是简单图，G的边色数为(G)或(G)+1.设G是二分图，G的边色数为(G).例题圈图Cn的边色数是多少？解解 Cn图的结点最大度数(Cn)=2.当n为偶数时，Cn图是二分图，边色数是(Cn)=2；当n为奇数时，Cn的边色数是3.如图8.4.9所示，图C4的色数是2，图C5的色数是3。例题某班同学期末共有7门课程考试，课程编号为1到7。已知一部分同学要参加1、2、6和7四门课程考试，一部分同学要参加1、2、3和7四门课程考试，一部分同学要参加1、5和6三门课程考试，一部分同学要参加3、4和7三门课程考试，一部分同学要参加3、4和5三门课程考试，试问如何安排考试时间，使得没有学生在同一时间有两门考试？对这个图的结点着色需要4种颜色，因而需要安排4个时间段考试
