第六章平面图与着色
第六章 平面图与着色
平面图 个图G能画在平面上,除顶点之外,再没有与 边相交,则称G为平面图。 画出的没有边交叉的图称为G的一个平面嵌入 的一个平面 在下图中2)是1)(K)的平面嵌入,所以(1)是平面图 单独看(2)是平面图,对于3)(K无论怎样画法也去不 掉交叉边,所以不是平面图。 个 (2) (3) (4)
平面图 一个图G能画在平面上，除顶点之外，再没有边与 边相交，则称G为平面图。 画出的没有边交叉的图称为G的一个平面嵌入或G 的一个平面。 在下图中(2)是(1) (K4 )的平面嵌入, 所以(1)是平面图, 单独看(2)也是平面图, 对于(3) (K5 )无论怎样画法,也去不 掉交叉边, 所以不是平面图。 (1) (2) (3) (4)
设G是一个连通的平面图,G的边将G所在的 平面划分成若干个区域,每个区坷称为G的一个面。 其中面积无限的区城称为无限面或外部面,常记 为R0,面积有限的区域称为有限面或内部面。 包圉每个面的所有边所构成的回路称为该面 的边界,边界的长度称为该面的次数,R次数记为 deg(r)o 对于非连通的平面图G可以类似地定义它的 面、边界及次数
设G是一个连通的平面图, G的边将G所在的 平面划分成若干个区域, 每个区域称为G的一个面。 其中面积无限的区域称为无限面或外部面, 常记 为R0 , 面积有限的区域称为有限面或内部面。 包围每个面的所有边所构成的回路称为该面 的边界, 边界的长度称为该面的次数, R次数记为 deg(R)。 对于非连通的平面图G可以类似地定义它的 面、边界及次数
例:下图为连通的平面图,共有3个面R,R1, R 2。 R的边界为初级回路vv3v4v1,deg(R1=3 R2的边界为初级回路v1Vv2v3v1,deg(R2)=3。 R无限面,它的边界为复杂回路 v1v4vsv6sv4Ⅴ3v2vⅥ1,deg(R0)=8。 R 6 5
v1 v2 v3 v4 v5 v6 R0 R1 R2 例：下图为连通的平面图, 共有3个面R0 , R1 , R2。 R1的边界为初级回路v1 v3 v4 v1 , deg(R1 )=3。 R2的边界为初级回路v1 v2 v3 v1 , deg(R2 )=3。 R0无限面, 它的边界为复杂回路 v1 v4 v5v6 v5 v4 v3 v2 v1 , deg(R0 )=8
又例:下图为非连通的平面图,有两个连 通分支,deg(R1)=3,deg(R2)=4,R的 边界由两个初级回路v1v2v3v1 和v4v5v6v7V围成,deg(R0)=7
v1 v2 v3 v4 v5 v6 v7 R1 R0 R2 又例：下图为非连通的平面图，有两个连 通分支， deg(R1 )=3， deg(R2 )=4， R0的 边界由两个初级回路v1 v2 v3v1 和v4 v5 v6 v7 v4围成， deg(R0 )=7
定理:设G=是有限平面图,有r个面, 则所有面的次数之和等于边数的2倍。即 ∑deg()=21E 证明:G的任何一边,或者是两个面的公共边界 为每一个面的次数增加1;或者在一个面中作为边界重 复计算两次,为该面的次数增加2。无论那种情况G的 任何一边为图中面的次数和增加2,故所有面的次数之 和等于边数的2倍
定理：设G=V,E是有限平面图，有r个面， 则所有面的次数之和等于边数的2倍。即 =2|E|。 证明：G的任何一边，或者是两个面的公共边界， 为每一个面的次数增加1；或者在一个面中作为边界重 复计算两次，为该面的次数增加2。无论那种情况G的 任何一边为图中面的次数和增加2，故所有面的次数之 和等于边数的2倍。 1 deg( ) r i i r =
设G为一个平面图,如果在G中任意不相邻 的两个顶点之间再加一条边,所得图为非平面图, 则称G为极大平面图 G 不是平面图
设G为一个平面图, 如果在G中任意不相邻 的两个顶点之间再加一条边, 所得图为非平面图, 则称G为极大平面图。 G G' 不是平面图
关于极大平面图有以下的几个结论: ①极大平面图是连通图。 ②结点数大于等于3的极大平面图不可能 存在割点和桥。 ③设G为结点数大于等于3的简单连通平 面图,G为极大平面图当且仅当G的每个面的次 数均为3
关于极大平面图有以下的几个结论： ①极大平面图是连通图。 ②结点数大于等于3的极大平面图不可能 存在割点和桥。 ③设G为结点数大于等于3的简单连通平 面图, G为极大平面图当且仅当G的每个面的次 数均为3
在非平面图G中任意删除一条边,所得图为平 面图,则称G为极小非平面图 例 G G
在非平面图G中任意删除一条边，所得图为平 面图, 则称G为极小非平面图。 例： G G
定理(欧拉公式):任意连通平面图G,若有n 个结点,m条边和r个面,则欧拉公式n-m+r=2 成立。 证明:对边数ml归纳证明。 (1)设m=0,由于G是连通图,所以G只能 是平凡图。这时,n=1,m=0,r=1,n-mr=2 成立。 (2)设m=k(k1)时欧拉公式成立,下证当 mF=k+1时,欧拉公式也成立
定理 (欧拉公式)：任意连通平面图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时，欧拉公式也成立