离散数学课件 第六章 特殊的图

离散数学

Discrete

Mathematics第六章特殊的图6.1欧拉图6.2哈密顿图6.3二部图6.4平面图6.5图的着点6.6应用26.1欧拉图第6章图

哥尼斯堡七桥问题欧拉图的定义欧拉图的判定定理欧拉图实例3离散数学哥尼斯堡七桥问题4离散数学18世纪中叶，欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的普雷格尔河，河中有两个小岛，由七座桥相连接，如图6.1（a）所示。当时人们热衷于讨论一个有趣的问题：游客按什么样的路线，能够从一个地点出发，将每座桥都通过一次且仅一次，最后回到出发地点？这就是著名的哥尼斯堡七桥问题，很长时间都没有人能解决这个问题。1736年，瑞士数学家欧拉（Euler）仔细研究了这个问题，他用4个点分别表示两个小岛和两岸，用连接两点的线段表示桥，如图6.1（b）所示。欧拉图的定义5定义6.1

经过图（无向图或有向图）中每条边一次且仅一次并且行遍图中每个顶点的回路（通路），称为欧拉回路（欧拉通路）。存在欧拉回路的图，称为欧拉图。半欧拉图:有欧拉通路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.离散数学欧拉图的判定定理6定理6.2无向图G有欧拉回路，当且仅当G是连通图且无奇度顶点。无向图G有欧拉通路、但无欧拉回路，当且仅当G是连通图且恰好有两个奇度顶点。这两个奇度顶点是欧拉通路的端点。定理6.2有向图G有欧拉回路，当且仅当G是强连通图且每个顶点的入度等于出度。有向图G有欧拉通路、但无欧拉回路，当且仅当G是单向连通的，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度小1，另一个顶点的入度比出度大1，欧拉通路以前一个顶点为始点，以后一个顶点为终点。离散数学欧拉图实例7例6.1

判断图6.2中各图是否有欧拉回路和欧拉通路。离散数学图6.2欧拉回路和欧拉通路问题根据定理6.1，图6.2（a）的4个顶点都是奇度顶点，无欧拉通路，更无欧拉回路。图6.2（b）有2个奇度顶点和2个偶度顶点，存在欧拉通路，但不存在欧拉回路。图6.2（c）中没有奇度顶点，存在欧拉回路，当然更有欧拉通路。故图6.2（c）是欧拉图，图6.2（a）和图6.2（b）都不是欧拉图。欧拉图实例(续)8例6.1

判断图6.2中各图是否有欧拉回路和欧拉通路。离散数学图6.2欧拉回路和欧拉通路问题由定理6.2，图6.2（d）既无欧拉回路，也无欧拉通路。图6.2（e）中存在欧拉通路，但无欧拉回路。图6.2（f）中存在欧拉回路，当然也存在欧拉通路。图6.2（f）是欧拉图，图6.2（d）和图6.2（e）都不是欧拉图。6.2哈密顿图第6章图

哈密顿周游世界问题哈密顿图的定义哈密顿通路和哈密顿回路的判定定理9离散数学哈密顿周游世界问题10与欧拉回路非常类似的问题是哈密顿回路问题。1859年,爱尔兰数学家威廉·哈密顿爵士（SirWillianHamilton）在给朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图6.3（a）中找到一条回路，使它经过这个图的所有顶点且每个顶点只经过一次？如果把每个顶点看成一个城市，连接两个顶点的边看成是道路，这个问题就等价于能否找到一条旅行路线，经过每一个城市恰好一次，再回到原来的出发地。他把这个问题称为周游世界问题。离散数学图6.3周游世界问题哈密顿图的定义11定义6.2给定图G，若存在一条通路经过图中的每个顶点恰好一次，则称这条路为哈密顿通路。若存在一条回路，经过图中的每个顶点恰好一次，则称这条回路为哈密顿回路。具有哈密顿回路的图称作哈密顿图。在图6.4所示的各图中，图6.4（a）中存在哈密顿通路，但不存在哈密顿回路。图6.4（b）中存在哈密顿回路，当然也存在哈密顿通路。图6.4（c）中既无哈密顿通路，更无哈密顿回路。图6.4（b）为哈密顿图，图6.4（a）和图6.4（c）都不是哈密顿图。离散数学图6.4哈密顿图问题哈密顿图的判定定理12定理6.3若图G=<V,E>具有哈密顿回路，则对于顶点集V的每个非空子集S均有成立。其中，W(G-S)是G-S中连通分支数。证明

设C是G的一条哈密顿回路，则对于V的任何一个非空子集S，在C中删去S中任一顶点v1，C-v1是连通的非回路；若再删去S中另一个顶点v2，则W(C-v1-v2）≤2。于是由归纳法可得：W(G-S)≤|2|。离散数学哈密顿图的判定定理13注意，定理6.3只是哈密尔图的一个必要条件并非充分必要条件因此满足定理结论条件的图并不一定是哈密顿图。例如著名的彼得森（Petersen）图（如图6.5所示）就满足定理结论条件，即对于顶点集的每个非空子集均有

成立但它不是哈密顿图。离散数学图6.5彼得森图哈密顿图的判定定理14定理6.4设G=<V,E>是n(n≥3)阶无向简单图。如果对G中任何一对不相邻的顶点u和v，都有d(u)+d(v)≥n-1，则在G中存在一条哈密顿通路。如果G中任何一对不相邻的顶点u和v，其度数之和都大于等于n，即d(u)+d(v)≥n，则G是哈密顿图。定理的条件对于图中哈密顿路的存在性只是充分条件，并不是必要条件。例如，设G是如图6.6所示6边形，虽然任何两个不相邻顶点的度数之和是4<6-1，但显然在G中有一条哈密顿通路。离散数学图6.6六边形哈密顿图的判定定理15离散数学关于有向图中的哈密顿图有以下定理：定理6.5设在n(n≥2)阶有向图G=<V,E>中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路.

6.3二部图第6章图

二部图的定义二部图的判定定理匹配（极大匹配,最大匹配,完美匹配,完备匹配）16离散数学二部图的定义17定义6.3设G=<V,E>是一个无向图，若能将其顶点集V划分为两个不相交的子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称为二部图（也称为偶图）。V1、V2称为互补顶点子集，此时可将记为G=<V1,V2,E>。若V1每个顶点与V2中每个顶点均有且仅有一边相关联，则称二部图G为完全二部图（或完全偶图）。当|V1|=n，|V2|=m时，完全二部图G记为Kn,m。图6.7中，（a）、（b）、（c）都是二部图，其中（c）是K3,3。离散数学图6.7二部图示例二部图的判定定理18定理6.6无向图G=<V,E>是二部图当且仅当G中没有长度为奇数的回路。例如，图6.8（a）中没有长度为奇数的回路，和图6.7（c）同构，因此是二部图。图6.8（b）中存在长度为奇数的回路，因此不是二部图。离散数学

（a）（b）图6.8判断是否为二部图匹配19定义6.4设G=<V,E>是一个无向图，M⊆E，若M中任意两条边均不相邻，则称M为G中的匹配。若在M中再加入任何一条边就不再是匹配，则称M为极大匹配。边数最多的匹配称为最大匹配，最大匹配中的条数称为G的匹配数，记为

1(G)，简记为

1

。设M为G中的一个匹配，v∈V(G)，若存在M中的边与v关联，则称v为M的饱和点，否则称v为M的非饱和点。若中每个顶点都是饱和点，则称M为完美匹配。离散数学匹配20在图6.9中，{e1}、{e2,e5}、{e3,e6,e7}、{e2,e4,e6}等都是匹配，其中{e2,e5}、{e3,e6,e7}、{e2,e4,e6}是极大匹配，{e3,e6,e7}、{e2,e4,e6}是完美匹配也是最大匹配，

1(G)=3。离散数学

图6.9无向图的匹配匹配21定义6.5设G=<V1,V2,E>是一个无向图，|V1|≤|V2|,M是G中一个最大匹配，若|M|=|V1|，

则称M为G中V1到V2的完备匹配。当|V1|=|V2|时，完备匹配是完美匹配.例6.2

假设有4个工人a1,a2,a3,a4，4项工作任务b1,b2,b3,b4，并且工人a1熟悉任务b1,b2,b4；a2熟悉任务b2,b3；a3熟悉任务b2,b4；a4熟悉任务b3,b4。建立二部图如图6.10（a）所示。那么，该如何给每个工人分配任务，使每个工人做一项任务，并且保证每个人做的都是自己熟悉的任务呢？解

图6.10（b）、图6.10（c）分别是一种分配方案，都是完美匹配。离散数学图6.10完美匹配示例6.4平面图第6章图

平面图的定义欧拉公式平面图的判断平面图的对偶图22离散数学平面图的定义23离散数学定义6.6设G=<V,E>是一个无向图，如果能够把G的所有顶点和边画在一个平面上，且使得任何两条边除了端点外没有其他的交点，则称G是一个平面图。画出的这种没有边交叉的图称为G的一个平面嵌入。图6.11（a）是完全图K4，图6.11（b）是它的一个平面嵌入，故K4是平面图。对于图6.11（c）所示的完全图K5，无论怎样画，也不能完全避免边的交叉，图6.11（d）是K5的边交叉最少的一种画法。图6.11平面图及其嵌入平面图的定义24离散数学定义6.7设G=<V,E>是一个平面嵌入，G的边将整个平面划分为若干区域，每个区域称为G的一个面，其中面积无限的区域称为无限面或外部面，常记为R0，面积有限的区域称为有限面或内部面。包围面的所有边构成的回路称为该面的边界，边界的长度称为面的次数，记为deg(R)。平面图的定义25离散数学图6.12（a）为连通的平面图，共有3个面R0、R1、R2。R1的边界为初级回路v3v4v6v3，deg(R1)=3。R2的边界为初级回路v4v5v6v4，deg(R2)=3。R0为无限面，边界为复杂回路v4v5v6v3v2v1v2v3v4，deg(R0)=8。图6.12（b）为非连通的平面图，有两个连通分支，共有3个面R0、R1、R2。deg(R1)=4，deg(R2)=3，R0为无限面，边界由两个初级回路v1v2v3v4v1和v5v6v7v5围成，deg(R0)=7。

图6.12平面图的面（a）(b)平面图的定义26离散数学定理6.7平面图的所有面的次数之和等于边数的2倍。证明

每条边可能在两个面的公共边界上，也可能只在一个面的边界上。当在两个面的公共边界上时，在每个面的边界上这条边出现一次，在计算总的次数时计数两次。而当它只在一个面的边界上时，它出现两次，在计算总的次数时也计算两次。所以所有面的次数之和等于边数的2倍。同一个平面图可以有不同形状的平面嵌入，但它们都是同构的。图6.13（b）与图6.13（c）都是图6.13（a）的平面嵌入，但形状不同。

图6.13平面图的不同平面嵌入欧拉公式27离散数学定义6.8设G=<V,E>是简单平面图，如果在G中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则称G为极大平面图。若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面图。K3、K4都是极大平面图。将K5和K3,3任意删除一条边后所得到图也是极大平面图。K5和K3,3都是极小非平面图。欧拉公式28离散数学定理6.8n(n≥3)阶简单平面图是极大平面图当且仅当它是连通的且每个面的次数都为3。根据此定理，图6.11（b）是极大平面图，图6.13（b）、图6.13（c）不是极大平面图，如果在这两图中对角的两个顶点之间添加一条边，便成为极大平面图（此时每个面的次数都为3），如图6.14所示。图6.14极大平面图欧拉公式29离散数学定理6.9(欧拉公式）

设G为任意的连通平面图，则有n

m+r=2.证

对边数m做归纳证明.(1)m=0时,G为孤立点，此时n=1，r=1，

结论自然成立.(2)设m=k-1(k1)结论为真，

要证明m=k结论成立:若G中至少有一个1度顶点。设v是1度顶点，删除v，得G=G-v，则G

是连通的,G

中有n=n-1个顶点,m=m-1条边，r=r.由归纳假设,n

-m

+r

=2，即(n-1)-(k-1)+r=2,整理后得n-k+r=2。若中所有顶点的度数大于或等于2，则必有初级回路。设C为一初级回路，在C上任取一条边e。令G=G-e，由于e在C上，所以G

仍连通。在G

中n=n，m=m-1，r=r-1，。由归纳假设得到n-(m-1)+(r-1)=2，即n-m+r=2证毕。欧拉公式30离散数学定理6.10设G为任意的连通平面图，且每个面的次数至少为l(l≥3),则

设G为有p(p

2)个连通分支的平面图,且每个面的次数不小于l(l

3),则证明

设G连通平面图，且每个面的次数至少为l，由定理6.7得2m≥lr，把欧拉公式代入上式，得2md≥l(2+m-n)，整理后得欧拉公式31离散数学推论

K5和K3,3不是平面图.证K5有5个顶点，10条边，假若是平面图，由于K5中无环和平行边，则每个面的次数均大于等于3，由定理6.10可得

矛盾，因而K5不是平面图。

类似地，K3,3有6个顶点，9条边，假若K3,3是平面图，由于中最短回路的长度为4，从而每个面的次数均大于等于4，因而有

矛盾，所以K3,3也不是平面图。平面图的判断32离散数学定义6.9设e=(u,v)为图的一条边，在G中删除e，增加新的顶点w，使u,v均与w相邻，称作在G中插入2度顶点w。设w为G中的一个2度顶点，w与u,v相邻，删除w，增加新边(u,v)，称作在G中消去2度顶点w。若两个图G1与G2同构，或经过反复插入、消去2度顶点后同构，则称G1与G2同胚。、定义6.10在图G中，删除e=(u,v)，用新的顶点w(可以用u或v充当w)取代u、v，并使w和除(u,v)外所有与u,v关联的边关联，称这个变换为边e的收缩。平面图的判断33离散数学定理6.11(库拉图斯基本理1)图G是平面图当且仅当G中既不含与K5同胚的子图，也不含与K3,3同胚的子图。定理6.12(库拉图斯基本理2)图G是平面图当且仅当G中既没有可以收缩到K5的子图，也没有可以收缩到K3,3的子图。例6.3

证明彼得森图不是平面图。证明

彼得森图见图6.15（a）,将其中的(a,f),(b,g)(c,h),(d,i),(e,j)收缩，得到图6.15（b），它是K5，由定理6.12，彼得森图不是平面图。图6.15彼得森图的收缩平面图的对偶图34离散数学定义6.11设G是一个平面图的平面嵌入,构造G*如下：在G的每一个面Ri中放置一个顶点vi*。设e为G的一条边，

若e在G的面Ri与Rj的公共边界上，则作边e*=(vi*,vj*)与e相交，且不与其他任何边相交。若e为G中的桥且在边Ri的边界上,则作以vi*为端点的环e*=(vi*,vi*)。称G*为G的对偶图。图6.16给出两个平面嵌入的对偶图，实线和空心点是平面嵌入，虚线和实心点是对偶图。实际上这两个平面嵌入是同一个图的平面嵌入。图6.16平面图的对偶图平面图的对偶图35离散数学平面图的对偶图有以下性质：（1）G*是平面图，而且是平面嵌入。（2）G*是连通图。（3）若e为G中的环，则G*中与e对应的边e*为桥；若e为桥，则G*中与e对应的边e*为环。（4）在多数情况下，G*为多重图（含平行边的图）。（5）同一个平面图的不同平面嵌入的对偶图不一定同构。例如图6.16中的两个对偶图不同构。平面图的对偶图的判断定理36离散数学定理6.13设平面图G是连通的，G*是G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数、边数和面数，则（1）n*=r。（2）m*=m。（3）r*=n。（4）设G*的顶点vi*位于G的面Ri中，则dG*(v*)=deg(Ri)。证明

由G*的构造可知，（1）、（2）显然成立。（3）由于都连通，因而满足欧拉公式：n-m+r=2n*-m+r*=2把（1）、（2）代入，可以推出。（4）设G的面Ri的边界为Ci，设Ci中有k1(k1≥0)条桥，k2条非桥的边，于是Ci的长度为k2+2k1，即deg(Ri)=k2+2k1。而k1条桥对应vi*处有个k1环，k2条非桥的边对应从vi*处引出k2条边，所以dG*(v*)=k2+2k1=deg(Ri)。平面图的对偶图的判断定理37离散数学定理6.14设平面图G有k个连通分支，G*是G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数、边数和面数，则（1）n*=r。（2）m*=m。（3）r*=n-k+1。（4）设G*的顶点vi*位于G的面Ri中，则dG*(v*)=deg(Ri)。定义6.12设G*是平面图G的对偶图，若G*≅G，则称为自对偶图。图中3个实线的图都是自对偶图，虚线的图是它们的对偶图。图6.17自对偶图6.5图的着点第6章图

着点色地图着色38离散数学着点色39离散数学定义6.13为无向图G的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称作图的一种点着色，简单称为着色，若能用k颜色给G的顶点着色，则称k可着色，若G为k点可着色的，但不是k-1可着色的，则称G的点色数为k，记作

𝜒(G)=k点色数的性质：性质一：𝜒(G)=1当且仅当是零图。性质二：𝜒(Kn)=n性质三：设G至少含一条边，则𝜒(G)=2当且仅当G为二部图。着点色40离散数学例6.4求环形图的点色数。图6.18环形图解（1）当n为偶数时，环形图是二部图，所以偶阶环形图的点色数为2。如图6.18（a）所示，环形图的点色数为2（顶点边标注的“1”或“2”分别代表两种颜色，下同）。（2）当为奇数时，环形图是二部图，所以它的点色数大于或等于3。任取其中一点，由于是二部图，所以存在2点可着色方案，于是就是3点可着色的。如图6.18（b）所示，环形图的点色数为3。着点色41离散数学例6.5

求轮形图Wn的点色数。（轮形图是一种特殊的图，由一个中心顶点和若干外围顶点构成。外围顶点形成一个闭合环，且都与中心顶点邻接。轮形图Wn中的n表示外围顶点的数量）。图6.19轮形图解

由于轮形图中包含了3阶环形图，所以轮形图的点色数大于或等于3。着点色42离散数学（1）当为偶数时，轮形图的一个3点着色方案是：将其中的偶阶环形图进行2点着色，将中心顶点着第3种颜色。所以当n为偶数时，轮形图Wn的点色数为3，如图6.19（a）所示，轮形图W6的点色数为3。（2）当n为奇数时，轮形图Wn不可能是3点可着色的，因为其中的奇阶环形图就需要3点着色，而中心顶点不可能用已用的3种颜色的任何一种进行着色。此时轮形图的一个4着色方案是：将其中的奇阶环形图进行3着色，将中心顶点着第4种颜色。所以当为奇数时，轮形图Wn的点色数为4。如图6.19（b）所示，轮形图W7的点色数为4。着点色43离散数学综合上面两个例子的结论，可以得到点色数的第四条性质：性质四：偶阶环形图的色数为2，奇阶环形图的色数为3；偶阶轮图的色数为3，奇阶轮图的色数为4。判断一个图是否可以用k种颜色着色是NP完全问题，现在已知的求图点色数的算法都具有指数阶的时间复杂度。下面给出韦尔奇鲍威尔(WelchPowell)点着色算法，它可以给出点色数一个较好的上界，其基本思想如下：Step1.将图中顶点按其度数递减的方式排成一个序列（如果有相同度数的顶点，这种序列是不唯一的）；Step2.用一种与所有已着色顶点颜色不同的新颜色C对序列最前面的尚未着色的顶点进行着色，并将与该顶点不邻接的且尚未着色的每一顶点着同样的颜色C；Step3.反复重复步骤Step2，直到所有顶点全部着上颜色为止；Step4.整个过程所用的颜色数即为该图的色数。地图着色44离散数学定义6.14连通且无桥的平面图的平面嵌入称为平面地图或地图，地图的面称为区域。若两个区域的边界至少有一条公共边，则称这两个区域是相邻的。定义6.15给地图G的每个区域涂上一种颜色，使相邻的区域涂不同的颜色，称为对G的面着色。若能用颜色给G面着色，则称G是K面可着色的。若G是K面可着色的，但不是K-1面可着色的，则称G的面色数为K。G的面色数记作𝜒*(G)=k。定理6.15地图G是k面可着色的当且仅当它的对偶图G*是k点可着色的。定理6.16（四色定理）任何平面图的面着色最多需要4种颜色。地图着色45离散数学地图着色可以转化成平面图的点着色.当G中无桥时,G*中无环.G的面与G*的顶点对应,且G的两个面相邻当且仅当G*对应的两个顶点相邻,从而G的面着色等同于G*的点着色。红红兰兰绿绿绿绿绿绿黄黄黄黄黄黄6.6应用第6章图

旅行商问题调度问题46离散数学旅行商问题47离散数学旅行商问题（TravelingSalesmanProblem，TSP）是一个经典的组合优化问题。假设有个城市，给定城市之间的道路的长度（长度可以为，对应两城市之间无交通线），其目标是找到一条最短路径，使得旅行商从一个城市出发，经过所有城市恰好一次后，最终返回原出发城市。TSP问题在运筹学、计算机科学和数学等领域具有重要的理论和实际意义。定义6.16

设图G=<V,E>（无向图或有向图），给定W:E->R，对G的每条边e，称W(e)为边e的权，把这样的图称作带权图，记作G=<V,E,W>。当e=(<u,v>)时，把W(e)记作W(u,v)。旅行商问题48离散数学TSP问题可以被定义为一个完全图的哈密顿回路问题，其中图的顶点代表城市，边代表城市间的路径，边的权重表示两个城市之间的距离。寻找最短路径的问题，就是找到一个总权重最小的哈密顿回路。采用图论的术语描述如下：设G=<V,E,W>是一个n阶带权完全无向图，其中每条边的权为非负实数且可以为∞，求G中一条最短的哈密顿回路。TSP问题的精确算法有暴力搜索法和动态规划法。暴力搜索法即将所有可能的路径都列举出来，计算每条路径的总距离，然后找出最短路径。下面举例说明：旅行商问题49离散数学例6.6

图6.20（a）所示为一个4阶带权图K4，求出其中最短的哈密顿回路。解

不计起点，也不计顺时针和逆时针，图中只有3条不同的哈密顿回路：C1=abcdaC2=abdcaC3=acbda分别如图6.20（b），（c），（d）所示，其长度分别为9，12，13。因此，C1是所求的最短路线。图6.20旅行商问题调度问题50离散数学图着色问题在多个领域有广泛应用，核心在于通过合理的颜色分配避免冲突或满足特定约束。其算法和理论在计算机科学、数学、工程等领域具有重要意义。以下是一些主要的应用场景：1.地图着色

【问题描述】为地图上的不同区域着色，使得相邻区域颜色不同。【应用】地图绘制、行政区划、地理信息系统（GIS）等。2.调度问题

【问题描述】将任务分配给资源（如时间、机器等），避免冲突。

【应用】考试安排、课程表安排、任务调度等。调度问题51离散数学3.寄存器分配

【问题描述】在编译器优化中，将变量分配到有限的寄存器上，避免冲突。

【应用】编译器设计、程序优化，提升代码执行效率。4.无线网络信道分配

【问题描述】为无线网络中的基站分配信道，避免干扰。

【应用】移动通信、Wi-Fi网络规划，优化网络性能。5.社交网络分析

【问题描述】为社交网络中的用户或群体着色，表示不同属性或类别。

【应用】社区检测、影响力分析、广告定向投放等