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

8.5特殊的图欧拉图汉密尔顿图平面图对偶图8.5特殊的图欧拉图

欧拉图

哥尼斯堡七桥问题：

18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。欧拉图 哥尼斯堡七桥问题：于是“七桥问题”就等价于上图能否一笔画成的问题。欧拉提出不存在一次走遍7座桥，而每座桥只许通过一次的走法。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成4个结点，7座桥表示成7条连接这4个结点的边，如下图所示。于是“七桥问题”就等价于上图能否一笔画成的问题。陆地是桥梁

定义1：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。

定义2：给定无孤立结点图G，若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图。v2v3v4v1（V1、V2、V3、V1、V4、V3）是一条欧拉路定义1：给定无孤立结点图G，若存在一条路，经过定理1：给定无向连通图G，G是欧拉图，当且仅当图中每个结点都是偶数度结点。定理2：无向图连通图G有一条欧拉路，当且仅当G有零个或两个奇数度结点。v2v3v4v1定理1：给定无向连通图G，G是欧拉图，当且仅当图中每个结点都

例：证明：n阶完全无向图Kn是欧拉图当且仅当n为奇数。

证：

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

是一条欧拉路。例：从图中找一条欧拉路。定理3：有向图G为欧拉图，当且仅当G是连通的，且每个结点入度等于出度。定理4：一个有向图G中具有欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小1，一个结点的入度比出度大1。定理3：有向图G为欧拉图，当且仅当G是连通的，且每个结点入度欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问题。邮递员一般的邮递路线是需要遍历某些特定的街道,理想地,他应该走一条欧拉路,即不重复地走遍图中的每一条边。有的邮递任务是联系某些特定的收发点,不要求走遍每一条边,只要求不重复地遍历图中的每一个顶点,此时感兴趣的是图中的顶点,这就是下面研究的汉密尔顿图。欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问汉密尔顿图1859年,爱尔兰数学家汉密尔顿(Halmiton)提出一个“周游世界”的游戏,它把图(a)所示的正十二面体的二十个顶点当作是地球上的二十个城市,要求旅游者从某个城市出发,沿棱走过每个城市一次且仅一次,最后回到出发点。(b)图中粗线所构成的回路就是问题的答案。ab汉密尔顿图1859年,爱尔兰数学家汉密尔顿(Ha

定义1：给定图G，若存在一条通路，经过图中的每个结点恰好一次，这条通路称作汉密尔顿路。

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

因为图G的汉密尔顿回路要经过节点v，这是显然deg(v)≥2，故G不是汉密尔顿图。例：证明：若一个无向图G=(V，E)存在一个节点v,使得定理1：若图G=<V，E>为汉密尔顿图，则对于结点集V的每个非空子集S(真子集S

)有：W(G-S)≤|S|成立，其中W(G-S)是G-S中的连通分支数。(必要条件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6定理1：若图G=<V，E>为汉密尔顿图，则对于结

定理2：设图G是有n个结点的简单无向图，若G中任意两个结点度数之和大于等于n，则G是汉密尔顿图。（这是充分条件，但不是必要条件）（a）（b）定理2：设图G是有n个结点的简单无向图，若G中任欧拉图和汉密尔顿图之间的区别：(1)欧拉回路是简单回路,而汉密尔顿图回路是基本回路。简单回路：各边都不相同的回路。基本回路：除终点与始点外，其它结点都不相同的回路。(2)欧拉图遍历边,而汉密尔顿图遍历顶点。欧拉图和汉密尔顿图之间的区别：(1)欧拉回路是简单回路,而

平面图例：K3,3图如下，试问：能否转变成与其等价的，且使得任何两条边除了端点外没有其它的交点的平面上的图？

456定义1：设G=<V,E>是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称G是一个平面图。平面图例：K3,3图如下，试问：能否转变成与其等判断一个图是否为平面图的简单方法是观察法：找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。如下图所示：但并非所有的图经过处理之后都可变为平面图。判断一个图是否为平面图的简单方法是观察法：但并非所有的

定义2：设G是一连通平面图，由图中的边所包围的区域，且在该区域内既不包含图的结点，也不包含图的边，这样的区域称为G的面。包围一个面的诸边称为此面的边界。面的面积为有限者称为有限面，面的面积为无限者称为无限面。

例：Ⅰ为有限面Ⅱ为无限面定义2：设G是一连通平面图，由图中的边所包围的区域，定义3：一个面的边界的回路长度称作是该面的次数，记为：deg(r)定理1：一个有限平面图，面的次数之和等于其边数的两倍。证明：对于G中的每一条边e，e或是两个面的公共边，或是在一个面中为悬挂边被作为边界计算两次，故定理成立。定义3：一个面的边界的回路长度称作是该面的次数，记为：deg

定理2：(欧拉定理)设图G是一个n个结点,m条边的连通平面图，它的面数为r，则有欧拉公式：

n－m＋r＝2。证明:用归纳法

m=0时，G为平凡图，n=1，r=1，公式成立。定理2：(欧拉定理)设图G是一个n个结点,m条边的连

设m=k-1（k≥1）时公式成立，现在考虑m=k时的情况。因为在连通图上增加一条边仍为连通图，则有三种情况：（1）所增边为悬挂边，此时G的面数不变，顶点数增1，公式成立。（2）在图的任意两个不相邻点间增加一条边，此时G的面数增1，边数增1，但顶点数不变，公式成立。（3）所增边为一个环，此时G的面数增1，边数增1，但顶点数不变，公式成立。设m=k-1（k≥1）时公式成立，现在考虑m=k时的

练习：在由6个结点，12条边构成的连通简单平面图中，每个面由几条边围成？练习：

定理3:设G是一个包含n个结点,m条边的连通简单平面图，且每个面的次数至少为l（l≥3），则定理3:设G是一个包含n个结点,m条边的连通简单平面于是有故

证明:由定理1(r为G的面数)再由欧拉公式n-m+r=2于是有故证明:由定理1(r为G的面数)再由欧拉公式

推论1:设图G是一个包含n个结点,m条边的连通简单平面图，若n≥3,则m≤3n-6。

证明：由于G是n≥3的简单连通平面图，所以G的每个面至少由3条边围成，即l≥3，由定理3得m≤3n-6.

推论1:设图G是一个包含n个结点,m条边的连通简单平面图推论1给出了平面图的必要条件，若不满足这些条件，则一定不是平面图。例：K5图不是平面图。推论1给出了平面图的必要条件，若不满足这些条件，则一定例：证明当每个结点的度数大于等于3时，不存在7条边的连通简单平面图。证：

(反证)：设G是(n，m)图，若m=7，根据推论1知，m≤3n-6，即7≤3n-6，于是3n≥13。根据握手定理，有即3n≤14。这与3n≥13矛盾。例：证明当每个结点的度数大于等于3时，不存在7条边的连练习：

(1)设G是包含n个结点(n≥3),m条边的连通简单平面图，证明G中至少有一个结点的度数小于等于5。(2)设G是包含n个结点(n≥3),边数m小于30的连通简单平面图，证明G中存在结点v,d(v)≤4。练习：

推论2:若连通简单平面图G不以K3为子图，则m≤2n-4。证明:由于G中不含K3，所以G的每个面至少由4条边围成，即l≥4，代入定理3，得m≤2n-4.推论2:若连通简单平面图G不以K3为子图，则例：证明K5和K3，3是非平面图。证明:假设K5是平面图，由推论1可知应有m≤3n-6，而当n=5，m=10时，这是不可能的，所以K5是非平面图。假设K3，3是平面图，因其不含子图K3，由推论2可知，当n=6，m=9时，m≤2n-4是不可能的，所以K3，3是非平面图。例：证明K5和K3，3是非平面图。(2)若e是G中两个不同面Ri和Rj的公共边，则存在且仅存在一条边e*k∈G*与e相交；(3)若e是一个面Ri内的边，则在G*中有一条与e交叉的环。则称G*为G的对偶图，G*与G互为对偶图。定义

设平面图G=〈V,E〉有r个面R1，R2，…，Rr，若有图G*=〈V*,E*〉满足下述条件：(1)Ri∈G，内部有且仅有一个结点v*i∈V*，i=1，2，…，r。1.对偶图

对偶图(2)若e是G中两个不同面Ri和Rj的公共边，则存在例:图（a）和（b）中，G*是G的对偶图，G的边用实线表示，G*的边用虚线表示。（a）（b）例:图（a）和（b）中，G*是G的对偶图，G的边用实线表示，2.着色问题在地图上，相邻国家涂不同的颜色，最少需要多少种颜色？100多年前，有人提出了“四色猜想”，即只用四种颜色就能做到，但一直无法证明，直到1976年美国数学家才用电子计算机证明了这一猜想。地图着色自然是对平面图的面着色，利用对偶图，可将其转化为相对简单的顶点着色问题，即对图中相邻的顶点涂不同的颜色。2.着色问题韦尔奇·鲍威尔（WelchPowell）给出了一种对图的着色方法，步骤如下：（1）将图G中的顶点按度数递减次序排列。（2）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种颜色。（3）按排列次序用第二种颜色对未着色的顶点重复（2）。用第三种颜色继续以上做法，直到所有的顶点均着上色为止。韦尔奇·鲍威尔（WelchPowell）给出了一种对图的着色例:用韦尔奇·鲍威尔法对下图着色。（1）各顶点按度数递减次序排列：c，a，e，f，b，h，g，d。（2）对c和与c不邻接的e，b着第一种颜色。（3）对a和与a不邻接的g，d着第二种颜色。（4）对f和与f不邻接的h着第三种颜色。例:用韦尔奇·鲍威尔法对下图着色。8.5特殊的图欧拉图汉密尔顿图平面图对偶图8.5特殊的图欧拉图

欧拉图

哥尼斯堡七桥问题：

18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。欧拉图 哥尼斯堡七桥问题：于是“七桥问题”就等价于上图能否一笔画成的问题。欧拉提出不存在一次走遍7座桥，而每座桥只许通过一次的走法。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成4个结点，7座桥表示成7条连接这4个结点的边，如下图所示。于是“七桥问题”就等价于上图能否一笔画成的问题。陆地是桥梁

定义1：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。

定义2：给定无孤立结点图G，若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图。v2v3v4v1（V1、V2、V3、V1、V4、V3）是一条欧拉路定义1：给定无孤立结点图G，若存在一条路，经过定理1：给定无向连通图G，G是欧拉图，当且仅当图中每个结点都是偶数度结点。定理2：无向图连通图G有一条欧拉路，当且仅当G有零个或两个奇数度结点。v2v3v4v1定理1：给定无向连通图G，G是欧拉图，当且仅当图中每个结点都

例：证明：n阶完全无向图Kn是欧拉图当且仅当n为奇数。

证：

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

是一条欧拉路。例：从图中找一条欧拉路。定理3：有向图G为欧拉图，当且仅当G是连通的，且每个结点入度等于出度。定理4：一个有向图G中具有欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小1，一个结点的入度比出度大1。定理3：有向图G为欧拉图，当且仅当G是连通的，且每个结点入度欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问题。邮递员一般的邮递路线是需要遍历某些特定的街道,理想地,他应该走一条欧拉路,即不重复地走遍图中的每一条边。有的邮递任务是联系某些特定的收发点,不要求走遍每一条边,只要求不重复地遍历图中的每一个顶点,此时感兴趣的是图中的顶点,这就是下面研究的汉密尔顿图。欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问汉密尔顿图1859年,爱尔兰数学家汉密尔顿(Halmiton)提出一个“周游世界”的游戏,它把图(a)所示的正十二面体的二十个顶点当作是地球上的二十个城市,要求旅游者从某个城市出发,沿棱走过每个城市一次且仅一次,最后回到出发点。(b)图中粗线所构成的回路就是问题的答案。ab汉密尔顿图1859年,爱尔兰数学家汉密尔顿(Ha

定义1：给定图G，若存在一条通路，经过图中的每个结点恰好一次，这条通路称作汉密尔顿路。

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

因为图G的汉密尔顿回路要经过节点v，这是显然deg(v)≥2，故G不是汉密尔顿图。例：证明：若一个无向图G=(V，E)存在一个节点v,使得定理1：若图G=<V，E>为汉密尔顿图，则对于结点集V的每个非空子集S(真子集S

)有：W(G-S)≤|S|成立，其中W(G-S)是G-S中的连通分支数。(必要条件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6定理1：若图G=<V，E>为汉密尔顿图，则对于结

定理2：设图G是有n个结点的简单无向图，若G中任意两个结点度数之和大于等于n，则G是汉密尔顿图。（这是充分条件，但不是必要条件）（a）（b）定理2：设图G是有n个结点的简单无向图，若G中任欧拉图和汉密尔顿图之间的区别：(1)欧拉回路是简单回路,而汉密尔顿图回路是基本回路。简单回路：各边都不相同的回路。基本回路：除终点与始点外，其它结点都不相同的回路。(2)欧拉图遍历边,而汉密尔顿图遍历顶点。欧拉图和汉密尔顿图之间的区别：(1)欧拉回路是简单回路,而

平面图例：K3,3图如下，试问：能否转变成与其等价的，且使得任何两条边除了端点外没有其它的交点的平面上的图？

456定义1：设G=<V,E>是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称G是一个平面图。平面图例：K3,3图如下，试问：能否转变成与其等判断一个图是否为平面图的简单方法是观察法：找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。如下图所示：但并非所有的图经过处理之后都可变为平面图。判断一个图是否为平面图的简单方法是观察法：但并非所有的

定义2：设G是一连通平面图，由图中的边所包围的区域，且在该区域内既不包含图的结点，也不包含图的边，这样的区域称为G的面。包围一个面的诸边称为此面的边界。面的面积为有限者称为有限面，面的面积为无限者称为无限面。

例：Ⅰ为有限面Ⅱ为无限面定义2：设G是一连通平面图，由图中的边所包围的区域，定义3：一个面的边界的回路长度称作是该面的次数，记为：deg(r)定理1：一个有限平面图，面的次数之和等于其边数的两倍。证明：对于G中的每一条边e，e或是两个面的公共边，或是在一个面中为悬挂边被作为边界计算两次，故定理成立。定义3：一个面的边界的回路长度称作是该面的次数，记为：deg

定理2：(欧拉定理)设图G是一个n个结点,m条边的连通平面图，它的面数为r，则有欧拉公式：

n－m＋r＝2。证明:用归纳法

m=0时，G为平凡图，n=1，r=1，公式成立。定理2：(欧拉定理)设图G是一个n个结点,m条边的连

设m=k-1（k≥1）时公式成立，现在考虑m=k时的情况。因为在连通图上增加一条边仍为连通图，则有三种情况：（1）所增边为悬挂边，此时G的面数不变，顶点数增1，公式成立。（2）在图的任意两个不相邻点间增加一条边，此时G的面数增1，边数增1，但顶点数不变，公式成立。（3）所增边为一个环，此时G的面数增1，边数增1，但顶点数不变，公式成立。设m=k-1（k≥1）时公式成立，现在考虑m=k时的

练习：在由6个结点，12条边构成的连通简单平面图中，每个面由几条边围成？练习：

定理3:设G是一个包含n个结点,m条边的连通简单平面图，且每个面的次数至少为l（l≥3），则定理3:设G是一个包含n个结点,m条边的连通简单平面于是有故

证明:由定理1(r为G的面数)再由欧拉公式n-m+r=2于是有故证明:由定理1(r为G的面数)再由欧拉公式

推论1:设图G是一个包含n个结点,m条边的连通简单平面图，若n≥3,则m≤3n-6。

证明：由于G是n≥3的简单连通平面图，所以G的每个面至少由3条边围成，即l≥3，由定理3得m≤3n-6.

推论1:设图G是一个包含n个结点,m条边的连通简单平面图推论1给出了平面图的必要条件，若不满足这些条件，则一定不是平面图。例：K5图不是平面图。推论1给出了平面图的必要条件，若不满足这些条件，则一定例：证明当每个结点的度数大于等于3时，不存在7条边的连通简单平面图。证：

(反证)：设G是(n，m)图，若m=7，根据推论1知，m≤3n-6，即7≤3n-6，于是3n≥13。根据握手定理，有即3n≤14。这与3n≥13矛盾。例：证明当每个结点的度数大于等于3时，不存在7条边的连练习：

(1)设G是包含n个结点(n≥3),m条边的连通简单平面图，证明G中至少有一个结点的度数小于等于5。(2)设G是包含n个结点(n≥3),边数m小于30的连通简单平面图，证明G中存在结点v,d(v)≤4。练习：

推论2:若连通简单平面图G不以K3为子图，则m≤2n-4。证明:由于G中不含K3，所以G的每个面至少由4条边围成，即l≥4，代入定理3，得m≤2n-4.推论2:若连通简单平面图G不以K3为子图，则例：证明K5和K3，3是非平面图。证明: