哈尔滨理工大学斛监課裎 离影数 第17章平面图及图的着色 计算机系
第17章 平面图及图的着色 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章说可 口本章的主要内容 平面图的基本概念 欢拉公式 平面图的判断 平面图的对偶图 顶点着色及点色数 地图的着色与平面图的点着色 边着色及边色数
本章说明 ❑本章的主要内容 –平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图 –顶点着色及点色数 –地图的着色与平面图的点着色 –边着色及边色数
本章所涉及到的图均指无向图
本章所涉及到的图均指无向图
口17.1平面图的基本概念 口17.2欧拉公式 口17.3平面图的判断 口17.4平面图的对偶图 口17.5图中顶点的着色 口17.6地图的着色与平面图的点着色 口17.7边着色 口口口 本章小结 习题 作业
❑ 17.1 平面图的基本概念 ❑ 17.2 欧拉公式 ❑ 17.3 平面图的判断 ❑ 17.4 平面图的对偶图 ❑ 17.5 图中顶点的着色 ❑ 17.6 地图的着色与平面图的点着色 ❑ 17.7 边着色 ❑ 本章小结 ❑ 习 题 ❑ 作 业
°17.1平面图的基本概念 关于平面图的一些基本概念 1、平面图的定义 口G可嵌入曲面S如果图G能以这样的方式画在曲面S上 ,即除顶点处外无边相交。 口G是可平面图或平面图若G可嵌入平面。 口G的平面嵌入—画出的无边相交的平面图 口非平面图—无平面嵌入的图
17.1 平面图的基本概念 一、关于平面图的一些基本概念 1、 平面图的定义 定义17.1 ❑ G可嵌入曲面S——如果图G能以这样的方式画在曲面S上 ，即除顶点处外无边相交。 ❑ G是可平面图或平面图——若G可嵌入平面。 ❑ G的平面嵌入——画出的无边相交的平面图。 ❑ 非平面图——无平面嵌入的图