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

平面图 1 平面图 定义 图G若能画在平面上 使任何两条边在顶 点之外都不相交 就称G可嵌入可嵌入平面 或称G是 可平面图可平面图 否则称不可平面图不可平面图 定义 可平面图的一个平面嵌入平面嵌入称为平面图平面图 在平面上画出 是图的一种表示方法 在平面上以边不交叉的方式画出 即平面图 平面图例 1 K4是可平面图 2 立方体是可平面图 3 面 定义 平面图G的某些边围成一个封闭区域 该区域内 任意两点间都可作一曲线相连 且该曲线不与任何顶点 和边相交 这种区域称为面面 面的边界边界 界定一个面的所有边 边界的边数称为面的度度 或次次 规定 割边计算两次 面与它边界上的边和顶点相关联相关联 面的周线周线 由边界构成且把面包含在内的圈 两个面若有公共边 则称相邻相邻 G有且只有一个无界面 即G外的区域 称为外部面外部面 其余面都称 内部面内部面 边界为何不一定是圈 因为割边的存在 例 面 边界 度 周线 相邻 面的度与边数 定理 平面图中面的度与图的边数m满足 f F G d f 2m 计算面的度时 割边要算2次 推论 平面图中奇度面数必为偶数 欧拉公式 定理 欧拉1852 设G是连通平面图 它的顶点 数n 边数m 面数r 之间有 n m r 2 证明思想 以每次加入一条边的方式来构造G 可 得G1 G2 Gm 归纳证明则Gk保持nk mk rk 2不变 推论 若平面图G有k个连通支 则 n m r k 1 2 不可平面图 定理 设G是简单连通平面图 若每个面的度 k 则 kr 2 m n 2 k k 2 例 K5是不可平面图 K5是结点数最少的不可平面图 例 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 否则可加边 如 11 极大可平面图的性质 定理 设G是n 3阶简单连通平面图 则 G是极大可平面图 G的面的度都是3 推论 设G是n 3阶简单平面图 则 m 3n 6 r 2n 4 等号成立 G是极大平面图 推论 简单平面图G中存在度小于6的顶点 12 对偶图 定义 给定图G 如下构造的图G 称为G的对偶 图 对偶 图 dual graph 1 G中每个面Ri内放一个G 顶点v i 2 对应面Ri和Rj的公共边e 作一条仅与e相交一 次的边e v i v j E G 3 若割边e在面Ri的边界上 则作v i上仅与e相交 一次的环e 13 例 对偶图 对偶图的性质 性质1 若G是平面图 则G必有对偶图G 且G 是 唯一的 可平面图的不同平面嵌入可有不同构的对偶图 性质2 G 是连通图 即使G不连通 性质3 若G是连通平面图 那么 G G 性质4 对连通平面图G及其对偶图G m m n d d n 有对偶图的充要条件 定理 G有对偶图 iff G是平面图 证 即性质1 即不可平面图没有对偶图 由Kuratowski定 理 不可平面图G一定含有同胚于K5或K3 3的子 图 因此若K5和K3 3没有对偶图 则G也没有对 偶图 利用性质4易验证K5和K3 3没有对偶图 平面图的着色 面着色问题 对平面图的面涂色 要求相邻面具 有不同颜色 定理定理 每一个平面图每一个平面图G都是都是5 可着色的可着色的 四色猜想 平面图的着色只需四色 1976年四色定理得到证明 Appel Haken 1996年Robertson Sanders Seymour和Thomas宣 布了一个更简单的证明并于1997年发表 趣题 Gardner的愚人节地图 Martin Gardner Scientific A