第6章平面图概要.pptx

第六章 平面图与着色;平面图 一个图G能画在平面上，除顶点之外，再没有边与边相交，则称G为平面图。 画出的没有边交叉的图称为G的一个平面嵌入或G的一个平面。 在下图中(2)是(1) (K4)的平面嵌入, 所以(1)是平面图, 单独看(2)也是平面图, 对于(3) (K5)无论怎样画法,也去不掉交叉边, 所以不是平面图。; 设G是一个连通的平面图, G的边将G所在的平面划分成若干个区域, 每个区域称为G的一个面。其中面积无限的区域称为无限面或外部面, 常记为R0, 面积有限的区域称为有限面或内部面。 包围每个面的所有边所构成的回路称为该面的边界, 边界的长度称为该面的次数, R次数记为deg(R)。 对于非连通的平面图G可以类似地定义它的面、边界及次数。;;;; 设G为一个平面图, 如果在G中任意不相邻的两个顶点之间再加一条边, 所得图为非平面图, 则称G为极大平面图。;关于极大平面图有以下的几个结论： ①极大平面图是连通图。 ②结点数大于等于3的极大平面图不可能存在割点和桥。 ③设G为结点数大于等于3的简单连通平面图, G为极大平面图当且仅当G的每个面的次数均为3。 ; 在非平面图G中任意删除一条边，所得图为平面图, 则称G为极小非平面图。 例： ; 定理 (欧拉公式)：任意连通平面图G，若有n个结点，m条边和r个面，则欧拉公式n-m+r=2成立。 证明：对边数m归纳证明。 ⑴设m=0，由于G是连通图，所以G只能是平凡图。这时，n=1，m=0，r=1，n-m+r=2成立。 ⑵设m=k (k≥1)时欧拉公式成立，下证当m=k+1时，欧拉公式也成立。 ; 若G是树，则G是非平凡树，则G中至少有两片树叶。设v为其中一片树叶。令G′=G-?v?(从G中删除结点v，而得到G′)，则G′仍然是连通图。设n′、m′和r′分别是G′的结点数、边数和面数。则n′=n-1，m′=m-1=k，r′ =r。于是n=n′+1，m=m′+1，r=r′。因为G′是连通图且m′=k，所以G′满足归纳假设的条件。由归纳假设知： n′-m′+r′ =2，所以 n–m+r=( n′+1)–(m′ +1)+r′= n′-m′ +r′ =2。 ; 若G不是树，则G中含有回路。设边e在G的某个回路上。令G′=G-?e?(从G中删除边e，而得到G′)，则G′仍然是连通图。设n′，m′和r′分别是的结点数、边数和面数。则n′=n，m′=m-1=k， r′=r–1。于是n=n′，m=m′+1，r=r′+1。因为G′是连通图且m′=k，所以G′满足归纳假设的条件。由归纳假设知：n′–m′＋r′=2，所以 n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2。 ;;定理 ：设G是连通的平面图，且每个面的次 数至少为l ( l ≥3），则 其中, n为G中的顶点数, m为边数。 ;;;库拉图斯基定理;定理 (库拉斯基定理) 一个图G是非平面的，当且仅当它包含一个同胚于K3.3或K5的子图。 例 说明彼得森图不是平面图。 解:删去下图(a)皮得森图的结点b,得其子图(b)H。而H胚于K3,3,所以皮得森不是平面图。;重要结论： (1)图G可嵌入球面?图G可嵌入平面。 (2)平面图的子图都是平面图。 (3) 非平面图的母图都是非平面图。 (4) 平面图在加环或平行边后还是平面图。;例： 立方体是平面图。;凸多面体;多面体的一些性质定理;正多面体 每个面且每个多面角都相等的凸多面体。 定理: 只有五个正多面体:四面体、立方体、十二面体、八面体、二十面体. 证明:设P是正多面体且G是对应的平面图,对任何 凸多面体均有: 因为P是正多面体,所以存在两个正整数h(?3) 和k(?3)使F=Fh且V=Vk,因此,有 -8=(h-4)Fh+(k-4)Vk,且hFh=2E=kVk,因3?h?5.;(1)当h=3时,有12=(6-k)Vk,由3?k?5. 当k=3时,V3=4,F3=4,此时P是四面体. 当k=4时,V4=6,F3=8,此时P是八面体 当k=5时,V5=12,F3=20,此时P是十二面体 (2)当h=4时,有8=(4-k)Vk,所以k=3,V3=8,F4=6,即 P是立方体. (3)