它的每个内部面少要由三条边围成,每条边最多为两个面.ppt

对于简单图来讲，它的每个内部面至少要由三条边围成，每条边最多为两个面的边界。 定理6.1：若连通平面图G有n个顶点,e条边和f个面,则n-e+f=2---称为欧拉公式 证明：对边数进行归纳证明: 对于一条边的连通平面图, 假设对于一切m-1条边的连通平面图, 欧拉公式均成立。现考察m条边的连通平面图。 (1)若G有一个度数为1的顶点, 则删去该顶点及其关联边, 便得到一个连通平面图G。 (2)若G中没有度数为1的顶点,则删去一个有界面边界上的任一条边,因为删去回路上的一条边不影响连通性，因此得到一个连通平面图G。 对于平面图，嵌如平面的画法可以有多种，但不管怎样，面数总是相等的。必须强调的是：欧拉公式只适用于连通平面图， 即任何一个连通平面图一定满足欧拉公式， 不满足欧拉公式的连通图一定不是平面图。 但是面数确定是比较困难的。 推论 6.1：若G是n?3的平面简单图, 则e?3n-6。 证明:显然只要对连通平面简单图证明即可。 设G 是n?3的连通平面简单图,G的每个面由三条或更多条边围成,因此边的总数s大于或等于3f(这里边的总数包括重复计算在内)。 即s?3f 由此定理我们可以证明K5是非平面图, 因为K5是连通的， n=5,e=10， 若K5是平面图，则由推论应该有e?3n-6 即10?3*5-6=9, 矛盾，所以K5不是平面图。 在这里要注意：对于n?3的平面简单图, 一定成立e?3n-6。 若e3n-6,则一定不是平面图。 但对于简单图，即使满足e?3n-6，也不一定是平面图。 例如，K3,3，n=6,e=9, 3n-6=3*6-6=129=e，成立，但K3,3不是平面图。 推论 6.2：若平面图的每个面由四条或更多条边围成, 则e?2n-4 证明：因为每个面由四条或更多条边围成，因此边的总数s大于或等于4f，即s?4f 证明K3,3不是平面图 例：小于30条边的连通平面简单图中存在顶点度数不超过4的顶点。 证明：若所有顶点度数都大于4，即G中所有顶点度数都?5。 二、平面图的特征 找出一个图是平面图的充分必要条件的研究曾经持续了几十年, 直到 1930 年库拉托斯基 (Kuratowski) 给出了平面图的一个非常简洁的特征。 首先介绍剖分的概念： 给定图G的一个剖分是对G实行有限次下述过程而得到的图: 删去它的一条边{u,v}后添加一个新的点w以及新的边{w,u}和{w,v}。 也就是说在G的边上插入有限个点便得到 G的一个剖分。 下图中给出了K5的一个剖分。 定理：(1)若图G的一个子图是Kn的剖分，则G中至少有n个顶点度数大于等于n-1； (2)若图G的一个子图是Kn,n的剖分，则G中至少有2n个顶点度数大于等于n。 例：G=(V,E)，|V|=7，若G中含有K5的剖分，则 不含有K5或K3,3的剖分. 定理 6.3 (库拉托斯基定理):图G是平面图当且仅当它的任何子图都不是K5或 K3,3的剖分。 上例中G是非平面图，而 是平面图 此定理告诉我们： (1)一个图是平面图，则不含有K5的剖分，也不含有K3,3的剖分。 (2)若图G不含有K5的剖分，也不含有K3,3的剖分。则G一定是平面图。 (3)若图G含有K5的剖分，则G一定不是平面图；若图G含有K3,3的剖分，则G一定不是平面图。 (4)若图G不是平面图，则或者G含有K5的剖分，或者G含有K3,3的剖分。 库拉托斯基定理虽然很漂亮, 但是在具体判定一个图是不是平面图时,这个定理并不能起作用。因此以后仍有许多这方面的研究工作。 在这里几何对偶常简称为对偶。 由定义可知,若G是连通平面图, 则G*也是连通平面图,而且G和G*的顶点数, 面数和边数有下列简单的关系。 定理 6.4：设G是有n个顶点,e条边,f个面的连通平面图;又设G的几何对偶G*有n*个顶点,e*条边,f*个面,则 n*=f,e*=e,f*=n。 由于平面图G的对偶G*也是平面图, 同样可对G*作几何对偶,记为G**。若G是连通的, 则G**与G之间有一个特别简单的关系, 如下所述。 定理 6.5：G是连通平面图当且仅当 G**同构于G。 由定义 6.3 的过程可知, 平面图G的任何两个几何对偶必同构。 又平面图G1与G2同构, 但未必G1*与 G2* 同构。关键是嵌入方式不同。 6.2顶点着色 定义 6.4:设G是一个没有自环的图, 对G的每个顶点着色, 使得没有两个相邻的顶点着上相同的颜色,这种着色称为图的正常着色。图G的顶点可用k种颜色正常着色, 称G为k-可着色的。使G是k-可着色的数k的最小值称为G的色数, 记为?(G)。如果?(G)=k,则称G是k色的。 如下图(a)中的图的色数是4, (b)中的图的色数是3。 设G是连通、没有自环的图,如果有多重边,则可删去多重边