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

推论2: 若连通简单平面图G不以K3为子图，则 m ≤ 2n- 4。 证明 :由于G中不含K3，所以G的每个面至少由4条边围成，即l ≥4，代入定理3，得m≤2n- 4. 例：证明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是非平面图。 (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. 对偶图 对偶图 例:图（a）和（b）中，G*是G的对偶图，G的边用实线表示，G*的边用虚线 表示。 （a） （b） 2. 着色问题 在地图上，相邻国家涂不同的颜色，最少需要多少种颜色？100多年前，有人提出了“四色猜想”，即只用四种颜色就能做到，但一直无法证明，直到1976年美国数学家才用电子计算机证明了这一猜想。 地图着色自然是对平面图的面着色，利用对偶图，可将其转化为相对简单的顶点着色问题，即对图中相邻的顶点涂不同的颜色。 韦尔奇·鲍威尔（WelchPowell）给出了一种对图的着色方法，步骤如下： （1）将图G中的顶点按度数递减次序排列。 （2）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种颜色。 （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着第三种颜色。 * * * * * 8.5 特殊的图 欧拉图 汉密尔顿图 平面图 对偶图 欧拉图 哥尼斯堡七桥问题： 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。 城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。 于是“七桥问题”就等价于上图能否一笔画成的问题 。 欧拉提出不存在一次走遍7座桥，而每座桥只许通过一次的走法。 陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成4个结点，7座桥表示成7条连接这4个结点的边，如下图所示。 定义1：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。 定义2：给定无孤立结点图G，若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图。 v2 v3 v4 v1 （V1、V2、V3、V1、V4、V3）是一条欧拉路 定理1：给定无向连通图G，G是欧拉图，当且仅当图中每个结点都是偶数度结点。 定理2：无向图连通图G有一条欧拉路，当且仅当G有零个或两个奇数度结点。 v2 v3 v4 v1 例：证明：n阶完全无向图Kn是欧拉图当且仅当n为奇数。 证： n阶完全无向图Kn是连通图且每个节点的度数均为n-1，于是Kn是欧拉图当且仅当n-1是偶数，即n为奇数。 例： 从图中找一条欧拉路。 解 ：有两个奇数度结点 : v1和v4，所以存在欧拉路。 L = v1,v2,v3,v4,v5,v2,v4 是一条欧拉路。 定理3：有向图G为欧拉图，当且仅当G是连通的，且每个结点入度等于出度。 定理4：一个有向图G中具有 欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小1，一个结点的入度比出度大1。 欧拉回路问题既是一个有趣的游戏问题, 又是一个有实用价值的问题。 邮递员一般的邮递路线是需要遍历某些特定的街道, 理想地, 他应该走一条欧拉路, 即不重复地走遍图中的每一条边。 有的邮递任务是联系某些特定的收发点, 不要求走遍每一条边, 只要求不重复地遍历图中的每一个顶点, 此时感兴趣的是图中的顶点, 这就是下面研究的汉密尔顿图。 汉密尔顿图 1859年, 爱尔兰数学家汉密尔顿(