电子科技大学：《图论及其应用 Graph Theory and its Applications》研究生课程教学资源（课件讲稿）19 平面图概念与性质

本次课主要内容 平面图概念与性质 (一)、平面图的概念 (二)、平面图性质 (三)、图的嵌入性问题简介 (四)、凸多面体与平面图

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：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件 间的导线间不能交叉。否则，当绝缘层破损时，会出现短 路故障。 显然，电路板可以模型为一个图，“要求电路元件间连 接导线互不交叉”，对应于“要求图中的边不能相互交叉

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 图的平面性问题是图论典型问题之一。生活中许多问题 都与该问题有关。 (一)、平面图的概念 例子1：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件 间的导线间不能交叉。否则，当绝缘层破损时，会出现短 路故障。 显然，电路板可以模型为一个图，“要求电路元件间连 接导线互不交叉”，对应于“要求图中的边不能相互交叉

例子2：空调管道的设计 某娱乐中心有6个景点，位置分布如下图。 >6 A2 分析者认为：(1)A,与A4,(2)A,与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 5 例子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 6 如果把每个景点分别模型为一个点，景点间连线，当且 仅当两景点间要铺设空调管道。那么，上面问题直接对应 的图为： A6 A5 A4 A3 A2 A1 于是，问题转化为：能否把上图画在平面上，使得边不 会相互交叉？

通过尝试，可以把上图画为： 于是，铺设方案为： 2

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 7 通过尝试，可以把上图画为： 于是，铺设方案为： A6 A5 A4 A3 A2 A1 A1 A4 A5 A3 A A2 6

例子3：3间房子和3种设施问题 问题：要求把3种公用设施（煤气，水和电）分别用煤气管 道、水管和电线连接到3间房子里，要求任何一根线或管道 不与另外的线或管道相交，能否办到？ 上面问题可以模型为如下偶图： H1 H2 H3 问题转化为，能否把上面偶图画在平面上，使得边与边 之间不会交叉？

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 8 问题：要求把3种公用设施(煤气，水和电)分别用煤气管 道、水管和电线连接到3间房子里，要求任何一根线或管道 不与另外的线或管道相交，能否办到？ 例子3：3间房子和3种设施问题 上面问题可以模型为如下偶图： H1 H2 H3 G W E 问题转化为，能否把上面偶图画在平面上，使得边与边 之间不会交叉？

上面的例子都涉及同一个图论问题：能否把一个图画在 平面上，使得边与边之间没有交叉？ 针对这一问题，我们引入如下概念 定义1如果能把图G画在平面上，使得除顶点外，边与边 之间没有交叉，称G可以嵌入平面，或称G是可平面图。可 平面图G的边不交叉的一种画法，称为G的一种平面嵌入， G的平面嵌入表示的图称为平面图。 H2 H3 H2 H3 图G 图G的平面嵌入

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 9 上面的例子都涉及同一个图论问题：能否把一个图画在 平面上，使得边与边之间没有交叉？ 针对这一问题，我们引入如下概念 定义1 如果能把图G画在平面上，使得除顶点外，边与边 之间没有交叉，称G可以嵌入平面，或称G是可平面图。可 平面图G的边不交叉的一种画法，称为G的一种平面嵌入， G的平面嵌入表示的图称为平面图。 H1 H2 H3 G W E 图G H3 H1 H2 G W E 图G的平面嵌入

注：(1)可平面图概念和平面图概念有时可以等同看待； (2)图的平面性问题主要涉及如下见个方面：1)平面图的 性质；2)平面图的判定；3)平面嵌入方法（平面性算法）；4) 涉及图的平面性问题的拓扑不变量。 由图的平面性问题研究引申出图的一般嵌入性问题的研 究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘 彦佩等在该方向都有重要结果。刘彦佩的专著是《图的上 可嵌入性理论》(1994)，化学工业出版社出版。 历史上，波兰数学家库拉托斯基、美国数学家惠特尼、 生于英国的加拿大数学家托特，我国数学家吴文俊等都在 拓扑图论中有过精湛的研究

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 10 注: (1) 可平面图概念和平面图概念有时可以等同看待； (2) 图的平面性问题主要涉及如下几个方面：1) 平面图的 性质；2) 平面图的判定；3) 平面嵌入方法(平面性算法) ;4） 涉及图的平面性问题的拓扑不变量。 由 图的平面性问题研究引申出图的一般嵌入性问题的研 究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘 彦佩等在该方向都有重要结果。刘彦佩的专著是《图的上 可嵌入性理论》(1994)，化学工业出版社出版。 历史上，波兰数学家库拉托斯基、美国数学家惠特尼、 生于英国的加拿大数学家托特，我国数学家吴文俊等都在 拓扑图论中有过精湛的研究

(二)、平面图性质 定义2(1)一个平面图G把平面分成若于连通片，这些连 通片称为G的区域，或G的一个面。G的面组成的集合用Φ 表示。 (2)面积有限的区域称为平面图G的内部面，否则称为G 的外部面。 平面图G 在上图G中，共有4个面。其中f是外部面，其余是内部 面。Φ={f1,f2,f3,4}

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 11 (二)、平面图性质 定义2 (1) 一个平面图G把平面分成若干连通片，这些连 通片称为G的区域，或G的一个面。G的面组成的集合用Φ 表示。 在上图G中，共有4个面。其中f4是外部面，其余是内部 面。Φ=｛f1, f2, f3, f4｝。 平面图G f1 f3 f2 f4 (2) 面积有限的区域称为平面图G的内部面，否则称为G 的外部面

(③)在G中，顶点和边都与某个给定区域关联的子图，称 为该面的边界。某面f的边界中含有的边数（割边计算2次） 称为该面f的次数，记为dg(f)。 平面图G 在上图中，红色边在G中的导出子图为面6的边界 deg(f)=1 deg(f,)=3 deg(f3)=6 deg(fa)=6 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 12 (3) 在G中，顶点和边都与某个给定区域关联的子图，称 为该面的边界。某面 f 的边界中含有的边数(割边计算2次) 称为该面 f 的次数, 记为deg ( f )。 平面图G f1 f3 f2 f4 在上图中，红色边在G中的导出子图为面 f3 的边界。 deg 1 ()1 f  deg 2 ()3 f  deg 3 ()6 f  deg 4 ()6 f  1、平面图的次数公式