离散数学-图论-平面图.pdf

平面图 1 平面图  定义:图G若能画在平面上,使任何两条边在顶 点之外都不相交, 就称G可嵌入平面,或称G是 可平面图.否则称不可平面图.  定义:可平面图的一个平面嵌入称为平面图.  在平面上画出是图的一种表示方法.  在平面上以边不交叉的方式画出,即平面图. 平面图例 1.K 是可平面图. 4 2.立方体是可平面图. 3 面  定义: 平面图G的某些边围成一个封闭区域, 该区域内 任意两点间都可作一曲线相连,且该曲线不与任何顶点 和边相交,这种区域称为面.  面的边界:界定一个面的所有边.  边界的边数称为面的度(或次).  规定:割边计算两次.  面与它边界上的边和顶点相关联.  面的周线:由边界构成且把面包含在内的圈.  两个面若有公共边,则称相邻.  G有且只有一个无界面,即G外的区域,称为外部面;其余面都称 内部面. 例:面,边界,度,周线,相邻  边界为何不一定是圈?  因为割边的存在 面的度与边数  定理:平面图中面的度与图的边数m满足 fF(G) d(f ) = 2m  计算面的度时, 割边要算2次.  推论:平面图中奇度面数必为偶数. 欧拉公式  定理(欧拉1852):设G是连通平面图,它的顶点 数n, 边数m, 面数r 之间有 n – m + r = 2 证明思想:以每次加入一条边的方式来构造G,可 得G , G , ... , G .归纳证明则G 保持n – m + 1 2 m k k k rk 2不变.  推论:若平面图G有k个连通支,则 n – m + r = k + 1 2 不可平面图  定理:设G是简单连通平面图.若每个面的度k, 则 kr/2 m (n – 2)k/(k – 2)  例: K 是不可平面图. 5  K 是结点数最少的不可平面图. 5  例: K3,3是不可平面图.  K3,3是n 6时边数最少的不可平面图. 8 Kuratowski定理  加细:在图的边上任意增加一些度为2的顶点.  原图与加细图称为同胚.  定理(Kuratowski):G是可平面图 G没有同胚 于K5和K3,3 的子图. 9 极大可平面图  设G是平面图,若在任意不相邻结点u和v之间加 入边(u,v)都会使G + (u,v)成为不可平面图,则称 G是极大可平面图.  注意:这里指的是加入边(u,v)在本质上破坏了图的可 平面性.  可能在一种平面表示下不能加,但在另一种表示下可 以加. 10 极大可平面图的性质  极大可平面图的简单性质: (1)必连通:否则可加边,如... (2)必无割点:否则可加边,如... (3)必无割边:否则可加边,如... (4)各面的度不能超过3:否则可加边,如...