合肥工业大学离散数学8.5.ppt

8.5平面图8.5.1平面图的概念8.5.2欧拉公式8.5.3库拉图斯基定理8.5.4正多面体8.5.5图的着色8.5.1平面图的概念若图G能够示画在平面内，且使得它的边仅在端点处相交，则称G是可平面图(plangraph)，已画在平面内的图称为G的平面表示。可平面图G与G的平面表示是同构的。在不产生混淆的情况下，这两个概念通常不加以区别，都简称为平面图(planargraph)。8.5.1平面图的概念例G2G4G6G1G3G58.5.1平面图的概念图的平面性易判断不？图的不可平面性易判断不？如果一个图是不可平面图，怎样将其画出才能使边相交次数最少，这个最少的边相交次数叫做图的交叉数。8.5.1平面图的概念完全二分图是平面图吗？其交叉数？G1G2G38.5.1平面图的概念完全图K5是最小阶不可平面图，其交叉数是1。G2G18.5.1平面图的概念二分图是平面图？二分图是平面图？当n≥3时，二分图是不可平面图？为什么？8.5.1平面图的概念定义8.5.1设G是一个平面图，由G中的边所包围的区域，在区域内既不包含G的结点，也不包含G的边，这样的区域称为G的一个面(face)。有界区域称为内部面，无界区域称为外部面。包围面的长度最短的闭链称为该面的边界。面的边界的长度称为该面的度数。8.5.1平面图的概念例8.5.1平面图的面、面的边界、面的度数。f1f2f3f4e1e7e10e8e9e3e5e4e2e67165342f58.5.1平面图的概念定理8.5.1对任何平面图G，面的度数之和为边数的二倍。？8.5.2欧拉公式定理8.5.2(欧拉公式)设平面图G有e条边，v个顶点和r个面，则v－e＋r＝2。证明(1)e＝1时，(2)假设公式对n条边的图G成立。设G有n＋1条边。8.5.2欧拉公式推论8.5.1设连通简单平面图G有e条边和v个顶点，其中v≥3，则e≤3v－6。证明G是简单图，G的每个面的度数至少为3。图G的面的度数之和2e≥3r(r为G的面数)。推论8.5.2设连通简单平面图G有e条边和v个顶点，v≥3且没有长度为3的圈，则e≤2v－4。证明G的每个面的度数至少为4。8.5.2欧拉公式推论8.5.3设G是任意平面图，则δ(G)≤5。证明设G有v个顶点e条边。若e≤6，结论显然；若e＞6，假设G的每个顶点的度数不小于6，则6v≤2e≤6v－12，因而假设不成立。8.5.3库拉图斯基定理定义8.5.2设G是一个平面图，通过删除G的一条边(x,y)，并且添加一个新结点a和两条边(x,a)与(a,y)，这样的操作称为初等细分。若可从相同图G通过一系列初等细分来获得图G1和G2，称G1和G2是同胚的(homeomorphism)。8.5.3库拉图斯基定理这三个图都同胚？ecbdaecbdabcead8.5.3库拉图斯基定理定理8.5.3一个图是非平面图，当且仅当它包含一个同胚于或K5的子图。例8.5.2彼得森(petersen)图不是平面图？ghijfdcebaghijfdcea8.5.3库拉图斯基定理彼得森(petersen)图同胚于？cgaeihfdjghijfdcea8.5.4正多面体凸多面体P对应连通可平面图G立方面体四面体8.5.4正多面体Euler凸多面体公式V－E＋F＝2V,E和F分别为多面体P的顶点数、棱数和面数8.5.4正多面体每个面并且每个多面角都相等的凸多面体称为正多面体(regularpolyhedrom)或Plato体。对应的平面图可称为Plato图。定理8.5.4仅有五个正多面体。8.5.5图的着色图的着色:给图的每个顶点都指定一种颜色，且相邻顶点指定不同的颜色。顶点着色图G的色数:着色图G所需要的最少颜色数。例8.5.3下图所示两图的色数分别是多少？8.5.5图的着色五色定理：连通简单平面图的色数不超过5。四色问题：连通简单平面图的色数不超过4。8.5.5图的着色1852年，德·摩根的学生Gurhrie提出四色问题1878年，著名数学家Cayley在伦敦数学会议公布1879年，Kempe给出一个证明