第六章平面图与着色
第六章 平面图与着色
平面图 个图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