第六章平面图 主要内容 一、 平面图概念与性质 二、特殊平面图与平面图的对偶图 三、平面图的判定与涉及平面性不变量 四、平面性算法 教学时数 安排8学时讲授本章内容
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第六章 平面图 主要内容 一、平面图概念与性质 二、特殊平面图与平面图的对偶图 三、平面图的判定与涉及平面性不变量 教学时数 安排8学时讲授本章内容 四、平面性算法
本次课主要内容 平面图概念与性质 (一)、平面图的概念 (二)、平面图性质 (三)、图的嵌入性问题简介 (四)、凸多面体与平面图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 本次课主要内容 (一)、平面图的概念 (二)、平面图性质 平面图概念与性质 (三)、图的嵌入性问题简介 (四)、凸多面体与平面图
(一)、平面图的概念 图的平面性问题是图论典型问题之一。生活中许多问题 都与该问题有关。 例子1：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件 间的导线间不能交叉。否则，当绝缘层破损时，会出现短 路故障。 显然，电路板可以模型为一个图，“要求电路元件间连 接导线互不交叉”，对应于“要求图中的边不能相互交叉
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 图的平面性问题是图论典型问题之一。生活中许多问题 都与该问题有关。 (一)、平面图的概念 例子1：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件 间的导线间不能交叉。否则，当绝缘层破损时，会出现短 路故障。 显然，电路板可以模型为一个图，“要求电路元件间连 接导线互不交叉”，对应于“要求图中的边不能相互交叉
例子2：空调管道的设计 某娱乐中心有6个景点，位置分布如下图。 分析者认为：(1)A1与A,(2)A2与A,(3)A3与A.间人流较 少，其它景点之间人流量大，必须投资铺设空调管道，但 要求空调管道间不能交叉。如何设计？
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 例子2：空调管道的设计 某娱乐中心有6个景点，位置分布如下图。 A1 A4 A5 A3 A A2 6 分析者认为：(1) A1与A4 , (2) A2与A5 , (3) A3与A6间人流较 少，其它景点之间人流量大，必须投资铺设空调管道，但 要求空调管道间不能交叉。如何设计？
如果把每个景点分别模型为一个点，景点间连线，当且 仅当两景点间要铺设空调管道。那么，上面问题直接对应 的图为： 于是，问题转化为：能否把上图画在平面上，使得边不 会相互交叉？
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 如果把每个景点分别模型为一个点，景点间连线，当且 仅当两景点间要铺设空调管道。那么，上面问题直接对应 的图为： A6 A5 A4 A3 A2 A1 于是，问题转化为：能否把上图画在平面上，使得边不 会相互交叉？