离散数学第八章(第4讲)课件.ppt

1、8.5 特殊的图特殊的图欧拉图欧拉图汉密尔顿图汉密尔顿图平面图平面图对偶图对偶图 欧拉图欧拉图 哥尼斯堡七桥问题：哥尼斯堡七桥问题：18世纪在哥尼斯堡城世纪在哥尼斯堡城(今俄罗斯加里宁格勒今俄罗斯加里宁格勒)的普莱格的普莱格尔河上有尔河上有7座桥，将河中的两个岛和河岸连结，如下图所座桥，将河中的两个岛和河岸连结，如下图所示。示。城中的居民经常沿河过桥散步，于是提出了一个问城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍题：能否一次走遍7座桥，而每座桥只许通过一次，最后座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。仍回到起始地点。这就是七桥问题，

2、一个著名的图论问题。n于是于是“七桥问题七桥问题”就等价于上图能否一笔画成的问题就等价于上图能否一笔画成的问题。n欧拉提出不存在一次走遍欧拉提出不存在一次走遍7座桥，而每座桥只许通过一次的走法。座桥，而每座桥只许通过一次的走法。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成4个结点，7座桥表示成7条连接这4个结点的边，如下图所示。定义定义1：给定无孤立结点图：给定无孤立结点图G，若存在一条路，经过图中每，若存在一条路，经过图中每边一次且仅一次，该条路称为边一次且仅一次，该条路称为欧拉路。欧拉路。定义定义2：给定无孤立结点图：给定无孤立结点图G，若存在一条回路，经过图中，若存在一条回路，经过

3、图中每边一次且仅一次，该回路称为每边一次且仅一次，该回路称为欧拉回路欧拉回路。具有欧拉回路的。具有欧拉回路的图称为图称为欧拉图欧拉图。v2v3v4v1（V1、V2、V3、V1、V4、V3）是）是一条欧拉路一条欧拉路n定理定理1：给定无向连通图：给定无向连通图G，G是欧拉图，当且仅当图是欧拉图，当且仅当图中每个结点都是中每个结点都是偶数度偶数度结点。结点。n定理定理2：无向图连通图：无向图连通图G有一条欧拉路，当且仅当有一条欧拉路，当且仅当G有有零个零个或或两个奇数度两个奇数度结点。结点。v2v3v4v1 例：证明：例：证明：n阶完全无向图阶完全无向图Kn是欧拉图当且仅当是欧拉图当且仅当n为奇数

4、。为奇数。证：证：n n阶完全无向图阶完全无向图K Kn n是连通图且每个节点的度数均为是连通图且每个节点的度数均为n-1n-1，于是，于是K Kn n是欧拉图当且仅当是欧拉图当且仅当n-1n-1是偶数，即是偶数，即n n为奇数。为奇数。例：例：从图中找一从图中找一条欧拉路。条欧拉路。解解：有两个奇数度结点：有两个奇数度结点:v1和和v4，所以存在欧拉路。，所以存在欧拉路。L=v1,v2,v3,v4,v5,v2,v4 是一条欧拉路。是一条欧拉路。n定理定理3：有向图：有向图G为欧拉图，当且仅当为欧拉图，当且仅当G是连通的，且每个结点是连通的，且每个结点入度等于出度。入度等于出度。n定理定理4：

5、一个有向图：一个有向图G中具有中具有 欧拉路，当且仅当它是连通的，欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小中，一个结点的入度比出度小1，一个结点的入度比出度大，一个结点的入度比出度大1。n欧拉回路问题既是一个有趣的游戏问题欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价又是一个有实用价值的问题。值的问题。n邮递员一般的邮递路线是需要遍历某些特定的街道邮递员一般的邮递路线是需要遍历某些特定的街道,理想地理想地,他应该走一条欧拉路他应该走一条欧拉路,即不重复地走遍图中的每一

6、条边。即不重复地走遍图中的每一条边。n有的邮递任务是联系某些特定的收发点有的邮递任务是联系某些特定的收发点,不要求走遍每一条不要求走遍每一条边边,只要求不重复地遍历图中的每一个顶点只要求不重复地遍历图中的每一个顶点,此时感兴趣的是此时感兴趣的是图中的顶点图中的顶点,这就是下面研究的汉密尔顿图。这就是下面研究的汉密尔顿图。汉密尔顿图汉密尔顿图 1859年年,爱尔兰数学家汉密尔顿爱尔兰数学家汉密尔顿(Halmiton)提出一个提出一个“周游世界周游世界”的游戏的游戏,它把图它把图(a)所示的正十二面体的二十个顶点当作是地球所示的正十二面体的二十个顶点当作是地球上的二十个城市上的二十个城市,要求旅游

7、者从某个城市出发要求旅游者从某个城市出发,沿棱沿棱走过每个城走过每个城市一次且仅一次市一次且仅一次,最后回到出发点最后回到出发点。(b)图中粗线所构成的回路图中粗线所构成的回路就是问题的答案。就是问题的答案。ab 定义定义1：给定图：给定图G，若存在一条通路，经过图中的每，若存在一条通路，经过图中的每个结点恰好一次，这条通路称作汉密尔顿路。个结点恰好一次，这条通路称作汉密尔顿路。定义定义2：给定图：给定图G，若存在一条回路，经过图中的每，若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。汉密尔

8、顿回路的图称作汉密尔顿图。例：例：(a)存在汉密尔顿回路,(a)是汉密尔顿图。(b)存在汉密尔顿通路但不存在汉密尔顿回路,(b)不是汉密尔顿图。(c)不存在汉密尔顿通路且不存在汉密尔顿回路,(c)不是汉密尔顿图。（a）（b）（c）练习：一只小蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，练习：一只小蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，最后回到原出发点？它爬过每一个顶点一次且仅一次，最后回到原出发点？例：证明：若一个无向图例：证明：若一个无向图G=(V，E)存在一个节点存在一个节点v,使得使得deg(v)=1，则，则G不是汉密尔顿图。不是汉密尔顿图。证证:因为

9、图因为图G的汉密尔顿回路要经过节点的汉密尔顿回路要经过节点v，这是显然，这是显然 deg(v)2，故，故G不是汉密尔顿图。不是汉密尔顿图。定理定理1：若图若图G=为汉密尔顿图，则对于结点集为汉密尔顿图，则对于结点集V的每个非空子集的每个非空子集S(真子集真子集S)有：有：W(G-S)|S|成立，其中成立，其中W(G-S)是是G-S中的连通分支数。中的连通分支数。(必要条件必要条件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6 定理定理2：设图设图G是有是有n个结点的简单无向图，若个结点的简单无向图，若G中任意中任意两个结点度数之和大于等于两个结点度数之和大于等于n，则，则 G 是

10、是 汉密尔顿图。汉密尔顿图。（这是（这是充分条件，充分条件，但不是但不是必要条件必要条件）（a）（b）欧拉图和汉密尔顿图之间的区别：欧拉图和汉密尔顿图之间的区别：(1)欧拉回路是欧拉回路是简单回路简单回路,而汉密尔顿图回路是而汉密尔顿图回路是基本回路基本回路。简单回路：简单回路：各边都不相同的回路。各边都不相同的回路。基本回路：基本回路：除终点与始点外，其它结点都不相同的回路。除终点与始点外，其它结点都不相同的回路。(2)欧拉图欧拉图遍历边遍历边,而而汉密尔顿汉密尔顿图图遍历顶点遍历顶点。平面图平面图 例例：K3,3图如下，试问：能否转变成与其等价的，且使得图如下，试问：能否转变成与其等价的，

11、且使得任何两条边除了端点外没有其它的交点的平面上的图？任何两条边除了端点外没有其它的交点的平面上的图？456定义定义1：设G=是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称G是一个平面图。判断一个图是否为平面图的简单方法是观察法：判断一个图是否为平面图的简单方法是观察法：找出基本循环，将交叉的边分别放置在基本循环内或找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。如下图所示：外而避免交叉。如下图所示：但并非所有的图经过处理之后都可变为平面图。定义定义2：设：设G是一连通平面图，由图中的边所包围的是一连通平面图，由图中的边所包围的区

12、域，且在该区域内既不包含图的结点，也不包含图区域，且在该区域内既不包含图的结点，也不包含图的边，这样的区域称为的边，这样的区域称为G的的面面。包围一个面的诸边称为此面的边界。包围一个面的诸边称为此面的边界。面的面积为有限者称为有限面，面的面积为无限者称面的面积为有限者称为有限面，面的面积为无限者称为无限面。为无限面。例：例：为有限面为无限面定义定义3：一个面的边界的回路长度称作是该面的次数，：一个面的边界的回路长度称作是该面的次数，记为：记为：deg(r)定理定理1：一个有限平面图，面的次数之和等于其边数：一个有限平面图，面的次数之和等于其边数的两倍。的两倍。证明证明：对于：对于G中的每一条边

13、中的每一条边e，e或是两个面的公共边，或是两个面的公共边，或是在一个面中为悬挂边被作为边界计算两次，故定或是在一个面中为悬挂边被作为边界计算两次，故定理成立。理成立。定理定理2：(欧拉定理欧拉定理)设图设图G是一个是一个n个结点个结点,m条边的连通条边的连通平面图，它的面数为平面图，它的面数为r，则有欧拉公式：，则有欧拉公式：nmr2。证明证明:用归纳法用归纳法 m=0时，时，G为平凡图，为平凡图，n=1，r=1，公式成立。，公式成立。设设m=k-1（k1）时公式成立，现在考虑）时公式成立，现在考虑m=k时的时的情况。因为在连通图上增加一条边仍为连通图，情况。因为在连通图上增加一条边仍为连通图

14、，则有三种情况：则有三种情况：（1）所增边为悬挂边，此时）所增边为悬挂边，此时G的面数不变，顶点的面数不变，顶点数增数增1，公式成立。，公式成立。（2）在图的任意两个不相邻点间增加一条边，此）在图的任意两个不相邻点间增加一条边，此时时G的面数增的面数增1，边数增，边数增1，但顶点数不变，公式，但顶点数不变，公式成立。成立。（3）所增边为一个环，此时）所增边为一个环，此时G的面数增的面数增1，边数增，边数增1，但顶点数不变，公式成立。，但顶点数不变，公式成立。练习：练习：在由在由6个结点，个结点，12条边构成的连通简单平面图中，每个条边构成的连通简单平面图中，每个面由几条边围成？面由几条边围成？

15、定理定理3:设设G是一个包含是一个包含n n个结点个结点,m,m条边的连通简单平面图，条边的连通简单平面图，且每个面的次数至少为且每个面的次数至少为 l（l 3），则），则(2)2lmnl于是有于是有22mrmnl(2)2lmnl故故 证明证明:由定理由定理112deg()riimRl r (r为为G的面数的面数)再由欧拉公式再由欧拉公式 n-m+r=2 推论推论1 1:设图G是一个包含n个结点,m条边的连通简单平面图，若n3,则m3n-6。证明证明：由于：由于G是是n 3的简单连通平面图，所以的简单连通平面图，所以G的每个的每个面至少由面至少由3条边围成，即条边围成，即l 3，由定理，由定理

16、3得得m3n-6.推论推论1给出了平面图的必要条件，若不满足这些条件，给出了平面图的必要条件，若不满足这些条件，则一定不是平面图。则一定不是平面图。例：K5 图不是平面图。图不是平面图。例：证明当每个结点的度数大于等于3时，不存在7条边的连通简单平面图。证：证：(反证反证)：设：设G是是(n，m)图，若图，若m=7，根据推论，根据推论1知，知，m3n-6，即，即73n-6，于是，于是3n13。根据握手定理，有。根据握手定理，有nvv3)deg(72 即 3n14。这与3n13矛盾。练习：(1)设G是包含n个结点(n3),m条边的连通简单平面图，证明G中至少有一个结点的度数小于等于5。(2)设G

17、是包含n个结点(n3),边数m小于30的连通简单平面图，证明G中存在结点 v,d(v)4。推论推论2:若连通简单平面图若连通简单平面图G不以不以K3为子图，则为子图，则 m 2n-4。证明证明:由于由于G中不含中不含K3，所以，所以G的每个面至少由的每个面至少由4条条边围成，即边围成，即l 4，代入定理，代入定理3，得，得m2n-4.例：证明例：证明K5和和K3，3是非平面图。是非平面图。证明证明:假设假设K5是平面图，由推论是平面图，由推论1可知应有可知应有m3n-6，而当而当n=5，m=10时，这是不可能的，所以时，这是不可能的，所以K5是非是非平面图。平面图。假设假设K3，3是平面图，因

18、其不含子图是平面图，因其不含子图K3，由推论，由推论2可可 知，当知，当n=6，m=9时，时，m2n-4是不可能的，所以是不可能的，所以 K3，3是非平面图。是非平面图。(2)若若e是是G中两个不同面中两个不同面Ri和和Rj的公共边，则存在且仅存在的公共边，则存在且仅存在一条边一条边e*k G*与与e相交；相交；(3)若若e是一个面是一个面Ri内的边，则在内的边，则在G*中有一条与中有一条与e交叉的环。交叉的环。则称则称G*为为G的对偶图，的对偶图，G*与与G互为对偶图。互为对偶图。定义定义 设平面图设平面图G=G=V,EV,E有有r r个面个面R R1 1，R R2 2，R Rr r，若有图

19、，若有图G G*=V V*,E,E*满足下述条件：满足下述条件：(1)(1)R Ri iGG，内部有且仅有一个结点，内部有且仅有一个结点v*i VV*，i i=1=1，2 2，r r。1.对偶图对偶图 对偶图对偶图 例例:图（图（a）和（）和（b）中，）中，G*是是G的对偶图，的对偶图，G的边用实线表的边用实线表示，示，G*的边用虚线的边用虚线 表示。表示。（a）（b）2.着色问题着色问题 在地图上，相邻国家涂不同的颜色，最少需要多少种在地图上，相邻国家涂不同的颜色，最少需要多少种颜色？颜色？100多年前，有人提出了多年前，有人提出了“四色猜想四色猜想”，即只用，即只用四种颜色就能做到，但一直

20、无法证明，直到四种颜色就能做到，但一直无法证明，直到1976年美年美国数学家才用电子计算机证明了这一猜想。国数学家才用电子计算机证明了这一猜想。地图着色自然是对平面图的面着色，利用对偶图，可地图着色自然是对平面图的面着色，利用对偶图，可将其转化为相对简单的顶点着色问题，即对图中相邻将其转化为相对简单的顶点着色问题，即对图中相邻的顶点涂不同的颜色。的顶点涂不同的颜色。n韦尔奇韦尔奇鲍威尔（鲍威尔（WelchPowell）给出了一种对图的着色）给出了一种对图的着色方法，步骤如下：方法，步骤如下：（1）将图）将图G中的顶点按度数递减次序排列。中的顶点按度数递减次序排列。（2）用第一种颜色对第一顶点着

21、色，并将与已着色顶点不）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种颜色。邻接的顶点也着第一种颜色。（3）按排列次序用第二种颜色对未着色的顶点重复（）按排列次序用第二种颜色对未着色的顶点重复（2）。）。用第三种颜色继续以上做法，直到所有的顶点均着上色为用第三种颜色继续以上做法，直到所有的顶点均着上色为止。止。例例:用韦尔奇用韦尔奇鲍威尔法对下图着色。鲍威尔法对下图着色。（1）各顶点按度数递减次序排列：）各顶点按度数递减次序排列：c，a，e，f，b，h，g，d。（2）对）对c和与和与c不邻接的不邻接的e，b着第一种颜色。着第一种颜色。（3）对）对a和与和与a不邻接的不邻接的g，d着第二种颜色。着第二种颜色。（4）对）对f和与和与f不邻接的不邻接的h着第三种颜色。着第三种颜色。aghfdcbe