平面图、对偶图和色数的应用探究-毕业论文

目 录1引言12相关概念和定理12.1 图的相关概念12.2 平面图的相关概念和定理22.3 对偶图的相关概念52.4 色数的相关概念和定理62.4.1 图中顶点的着色62.4.2 边着色62.4.3 面着色73平面图、对偶图和色数的应用73.1 平面图理论的应用73.2 对偶图理论的应用93.3 色数理论的应用103.3.1 运用图论知识解决高中数学染色问题103.3.2 染色理论在教务工作中的两个应用124结束语15参考文献16致谢17平面图、对偶图和色数的应用探究 xxx本xxx班 xxx 指导老师 xxx摘 要：平面图、对偶图和色数理论不仅是图论中的重要内容,而且在实际生活中应用广泛。本文首先阐述了平面图、对偶图和色数的相关概念和定理，然后分别探究了其实际应用。其中，景区空调管道的设计和3间房子3种设施问题是典型的平面图模型，电力电子器件的对偶变换是对偶图理论的应用，高中数学染色问题的图论解法和教务工作中期末考试安排和排课表问题是平面图的色数理论的应用。 关键词：平面图，对偶图，色数，应用探究。The application of planar graph, dual graphs and chromatic numberXxxxxxxxxxxxxxx Class xxxx, Mathematics DepartmentTutor: xxxxxxxx Abstract: plan, dual graphs and chromatic number theory is not only the important content in graph theory, and extensive application in real life. This paper firstly explains the related concept plan, dual graphs and chromatic number and theorem, and then explores its practical application. Among them,the scenic design of air conditioning pipeline and 3 houses 3 facilities is a plane graph model, dual transformation of power electronic devices is the application ofthe dual graph coloring problem, high school mathematics graph theory method and the final exam schedule administration work and the timetable problem is the application of chromatic number of planar graphs of theory. Key words: plan, dual graph, chromatic number, application research. ii1引言 图论起源于著名的哥尼斯堡七桥问题，欧拉在1736年解决了这个问题，并于1753年发现了欧拉公式而成为拓扑图论的奠基人。接着中断了170多年。1930年，当波兰数学家C.Kuratowski和美国数学家O.Frink & P.A.Smith发现了平面图判定准则后，这方面的研究才开始复苏。20世纪70年代，我国著名数学家吴文俊教授和刘彦佩教授创立了平面性判定的“吴-刘”方法得到了国际数学界的认可。如今，平面问题的研究成果已经在交通网络和印刷线路的设计等方面得到应用。世界上著名的“四色猜想”曾困扰了数学家们将近100年，期间人们进行了各种尝试，平面图的对偶图也曾用于解决著名的四色猜想问题，但都以失败告终，最后数学家凯尼斯.阿佩尔和沃夫冈.哈肯借助计算机得以解决。平面图的染色问题是与四色问题紧密相联的。于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色？这个问题叫做图的点着色问题。如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色？这个问题叫做边的着色问题，边的着色问题可以转化为点着色问题。由于生产管理、军事、交通运输等方面提出大量实际问题的需要，图的染色理论及其应用研究得到飞速发展。2相关概念和定理 2.1图的相关概念 定义1 一个图是一个三元组, 其中为有限非空结点集合, 称为结点, 为有限的边集合, 称为边, 是从边集合到结点对集合上的函数. 图可简记为:. 定义2 如果中边对应V中的结点对是无序的, 称是无向边, 记, 称,是的两个端点. 如果与结点有序对相对应, 称是有向边, 记, 称为的始点, 为的终点. 定义3 每条边均为无向边的图称为无向图. 每条边均为有向边的图称为有向图. 有些边是无向边, 有些边是有向边的图称为混合图. 定义4 设, 为两个图(同时为无向图或有向图), 若且, 则称为的子图, 为的母图, 记作. 若是 的子图, 且或, 则称为的真子图. 若是的子图, 且, 则称为的生成子图.定义5 两个图和, 如果它们的结点间存在一一对应关系（双射）, 而且这种对应关系也反映在表示边的结点对中(如果是有向边则对应的结点对还保持相同的顺序), 则称这两图是同构的, 记作. 特别申明, 本文所涉及到的图均指无向图.2.2 平面图的相关概念和定理定义1 设图是一个无向图, 如果能够把的所有结点和边画在平面上, 且使得任何两条边除了端点外没有其他的交点, 就称是一个平面图.注意: 有些图从表面上看有几条边是相交的, 但是改画之后, 仍然是平面图. 图1 图2 图3图3是非平面图 图4是非平面图 图4定义2 设是一个连通平面图, 由图中的边所包围的区域, 在区域内既不包含图的结点, 也不包含图的边, 这样的区域称为的一个面, 包围该面的诸边所构成的回路称为这个面的边界. 面的边界的回路长度称作该面的次数, 记为.定义3 路图, 即每个点只与其相邻的2个或1个点相连,首位不连的平面图, 如图5. 个顶点,条边的路图用表示.图5定义4 圈图, 即首尾相连的路图,如图6. 个顶点,条边的圈图用表示. 图6 定义5 轮图, 即圈图的中间还有一个点,该点与圈上每个点有一条连线的平面图, 如图7. 个顶点,条边的轮图用表示.图7定义6 完全图, 即每两个顶点之间都有一条边相连的平面图, 如图8. 个顶点,条边的完全图用表示. 图8定义7 数图, 即不包含圈的图, 如图9.图9定理1 （欧拉定理）设有一个连通的平面图, 共有个结点条边和个面,则欧拉公式成立.定理2 设是一个有个结点条边的连通简单平面图, 若, 则.推论 如果图是连通的简单平面图, 若, 且每个区域至少由四条边围成, 则有.2.3对偶图的相关概念 定义1 给定平面图, 它具有面, 若有图 满足下列条件: (a) 对于图的任何一个面, 内部有且仅有一个结点; (b) 对于图的面和的公共边界, 有且仅有一条边, 使得, 且 与相交; (c) 当且仅当只是一个面的边界时, 存在一个环与相交, 则称是的对偶图. 定义2 若图的对偶图同构于, 则称是自对偶图. 定理1 设是连通平面图的对偶图, , , 和 , , 分别为和的顶点数、边数和面数, 则 (1) ; (2) ; (3) ; (4) 设的顶点位于的面中, 则.定理 2 设是具有个连通分支的平面图的对偶图, 则(1) ;(2) ;(3);(4) 设位于的面中, 则, 其中, , , , , 同前.2.4色数的相关概念和定理2.4.1图中顶点的着色 定义1 图的一种着色, 即对无环图的每个顶点涂上一种颜色, 使相邻顶点涂不同的颜色. 定义2 对进行着色（是可着色的）, 即能用种颜色给的顶点着色. 定义3 的色数, 即是可着色的, 但不是可着色的. 定理1 当且仅当为零图. 定理2 . 定理3 设中至少含有一条边, 则当且仅当为二部图. 定理4 对于任意无向图, 均有. 定理5 圈图着色定理: 用(为正整数) 种颜色给圈图的顶点着色, 方法数为:, 其中, .定理6 轮图着色定理: 用(为正整数)种颜色给轮图的顶点着色, 方法数为:,其中,. 推论1 圈图上一个指定的顶点染指定的颜色, 方法数为,. 推论2 圈图上两个指定相邻的顶点染指定的不同的颜色, 方法数为, .2.4.2边着色 定义1 对图边的一种着色, 即对图的每条边涂上一种颜色, 使相邻的边涂不同的颜色. 定义2 是边可着色的, 即能用种颜色给的边着色. 定义3 的边色数, 即是边可着色的, 但不是边可着色的, 也就是说最少用种颜色给的边着色. 定理1 为简单平面图, 则.定理2 若是二部图, 则. 2.4.3面着色 定义1 是面可着色的, 即能用种颜色给的面着色, 就称对的面进行了着色.定义2 的面色数, 即是面可着色的, 但不是面可着色的, 也就是说最少用种颜色给的面着色.定理1 图是面可着色的当且仅当它的对偶图是点可着色的.定理2 任何平面图都是可着色的. 3平面图、对偶图和色数的应用3.1平面图理论的应用 例1 (空调管道的设计) 某娱乐中心有6个景点, 位置分布如下图.图10 经考察知, 与、与、与间人流较少, 其它景点之间人流量大, 必须投资铺设空调管道, 但要求空调管道间不能交叉. 如何设计? 如果把每个景点分别模型为一个点, 景点间连线, 当且仅当两景点间要铺设空调管道. 那么, 上面问题直接对应的图为:图11 于是, 问题转化为, 能否把上图画在平面上, 使得边不会相互交叉?通过尝试, 可以把上图画为:图12 于是, 铺设方案为:图13 例2（3间房子和3种设施问题）要求把3种公用设施(煤气、水和电)分别用煤气管道、水管和电线连接到3间房子里, 要求任何一根线或管道不与另外的线或管道相交, 能否办到? 经分析知,上面问题可以模型为如下偶图: 图14 问题转化为, 能否把上面偶图画在平面上, 使得边与边之间不会交叉? 该图有6个结点, 9条边, 此时926-4=8, 根据2.2定理2的推论知, 此图不是平面图, 即任何一根线或管道不与另外的线或管道相交是不可能的.3.2对偶图理论的应用 电力电子电路中包括很多电力电子器件, 在对电路进行对偶变换时, 需要将各种器件变成相应的对偶器件. 对于线性器件, 具有对偶关系的器件包括: 电阻元件与电导元件, 电容元件与电感元件, 电压源与电流源等. 电力电子器件主要是非线性的开关器件, 非线性电力电子器件的对偶定义为: 非线性器件的对偶,就是在其理想静态开关特性曲线上, 电压轴与电流轴互换; 在动态特性方面, 可控开通与可控关断呈对偶关系, 可控开通与不可控开通也呈对偶关系; 同理, 不可控开通与不可控关断, 以及可控关断与不可控关断都是对偶的.根据定义, 表1 列出了几种常见开关器件的对偶器件.表1 常见开关器件的对偶3.3色数理论的应用3.3.1运用图论知识解决高中数学染色问题 例1 ( 2007 天津高考题) 如图15, 用6 种不同的颜色给四个格子染色, 每个格子涂一种颜色, 要求最多使用3 种颜色且相邻的两个格子颜色不同, 则不同的染色方法共有_种. 图15常规解法: 分2 种染色与3 种染色讨论, 共390 种.图论解法: 此题可以转化为路图的3 染色与2 染色问题, 的染色方法数为. 所以, 例1 的解答为: . 例2 ( 2008 全国卷高考题) 如图16, 一环形花坛分成, , , 四块,现有4 种不同的花供选种, 要求在每块里种1 种花, 且相邻的2 块种不同的花,则不同的种法总数为_. 图16常规解法: .图论解法: 此题可以先假设中间也有一种花, 问题即转化为轮图的的5染色问题, 最后再除以中间的5种不同染色方案即可. 所以, 例2的解答就为:. 例3 ( 2003 广东高考题) 如图17, 一个地区分为5个行政区域, 现给地图着色, 要求相邻区域不得使用同一颜色. 现有4种颜色可供选择, 则不同的着色方法共有_种. 图17 常规解法: 分2、4 同花与2、4 不同花两种情况讨论或是枚举法, 共72 种. 图论解法: 此题可以直接转化为轮图的的4染色问题, 解法为:.由于点的着色与面的着色是等价的, 所以我们将例1至例3中的问题转化为图中的图的染色问题, 这为我们解决问题带来了方便. 特别是遇到一些需要烦琐的枚举或是分多种类型进行思考的问题, 图论方法也可以作为检验常规方法是否做对的一个有效工具. 由此可见, 利用图论知识解决高考中的染色问题会带来很大的方便, 运用图论知识解决高中数学中的染色问题也是十分可行的.3.3.2染色理论在教务工作中的两个应用 例1 学院某学期开设高等数学、线性代数、概率统计、计算机基础4门公共课和数学分析、高等代数、常微分方程数值解、数据库原理及应用计算机网络8门专业课, 这12门课程都将进行期末考试, 其中8名教师开课情况如表2所示:表2：开课表教师开设的课程甲高等数学、线性代数、高等代数乙高等数学、概率统计、常微分方程丙高等数学、数学分析丁高等数学、概率统计、微分方程数值解戊线性代数、高等代数、复变函数己数学分析、常微分方程庚概率统计、计算机基础、数学模型辛计算机基础、计算机网络、数据库原理及应用 同名课程必须同时考试, 要求每位教师必须监考自己所任课程, 且每天只监考一门科目. 假设考试教室相对充足, 且每人都希望尽早结束考试投入假期生活.问该学期的期末考试最少要几天才能完成? 解 设公共课高等数学、线性代数、概率统计、计算机基础的课程编号分别为，; 专业课数学分析、高等代数、常微分方程、复变函数、数学模型、微分方程数值解、数据库原理及应用、计算机网络的课程编号分别为1, 2, 3, 4, 5, 6, 7, 8. 以结点代表课程, 以课程编号作为结点标记, 构造课程图: 如果某两门课程是由同一名教师开设的, 则将相应结点之间连一条边, 得到一个图, 使用最短的时间考试等价于对使用种颜色的染色. 对图进行正常的顶点染色,满足相邻的两点染不同的颜色, 则同色的顶点可以安排在同一天进行考试.这样, 每位教师就不会出现监考冲突的现象.算法思想: 从顶点度数最小的顶点开始染色, 找到不与其相邻的顶点并选择其中一个顶点进行染色, 再找与这两个顶点都不相邻的顶点集合, 并对其中一个顶点染色, 直到找不到为止. 再找未染色的度数小的顶点, 重复进行以上过程,直到所有顶点都已染色为止, 程序结束.按照以上算法对图染色, 于是本题的一种染色方案为点4、5、7染红色; 点1、8染绿色; 点2、3、6、染蓝色. 如图18所示: 图18：课程图 由以上的染色结果得到=3, 即学院这学期的期末考试三天就可以完成.具体安排可以为: 第一天考高等数学、复变函数、数学模型、数据库原理及应用; 第二天考线性代数、概率统计、数学分析、计算机网络; 第三天考计算机基础、高等代数、常微分方程、微分方程数值解.例2 五名教师, , , , 给八个班级, , , , , , , 授课, 教学要求可参照关联矩阵: =, 其中中元素表示教师有班级的课程数, 问: 一天至少要安排几节课才能完成教学要求, 并排出相应的课表.解 分别以=, , , , ,=, , , , , , , 为顶点构造二布图=, =1时, 在和间连一条边, 得到图,一天安排最少的课程数实际上就是对使用种颜色的边染色, 由2.4.2的定理2可得=5.算法思想: 从图的任一条边染色, 然后找到一条不与其相邻的边进行染色, 再找与两条边都不相邻的一条边进行染色, 直到没有可以染色的边为止; 再找一条没有染色的边重复上述过程, 直到所有边都已染色为止, 程序结束. 按照以上的算法对图进行边染色, 本题的一种染色方案为, , , 染红色; , , , , 染黑色; , , , , 染绿色; , , , , 染蓝色; , , , 染黄色. 如图19所示: 图19：教学图 于是一天至少安排5节课, 按照以上染色情况可排出相应的课表. 如:红色的第一节上, 黑色的第二节上, 绿色的第三节上, 蓝色的第四节上, 黄色的第五节上, 见表3:表3: 课表安排节次班级教师第一节第二节第三节第四节第五节4结束语 通过收集、查阅大量的资料，本文总结归纳了平面图、对偶图和色数的相关概念和定理，在此基础上分别探究了它们在实际生活中的应用。平面图、对偶图和色数的应用很多，本文只是简单介绍了它们的几个典型应用，我们主要是体会其思想和方法。参考文献1 J.A.邦迪U.S.R.图论及其应用M.北京: 科学出版社,1984. 2 徐俊明.图论及其应用M. 北京:中国科学技术大学出版社,2010.3 史天治.平面图与对偶原理J.长春师范学院学报,2006,10:38-40.4 王绍文.图的