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

1、i目 录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致谢 .17ii平面图、对偶图和色数的应用探究xxx 本 xxx 班 xxx指导老师

2、xxx摘 要：平面图、对偶图和色数理论不仅是图论中的重要内容,而且在实际生活中应用广泛。本文首先阐述了平面图、对偶图和色数的相关概念和定理，然后分别探究了其实际应用。其中，景区空调管道的设计和 3 间房子 3 种设施问题是典型的平面图模型，电力电子器件的对偶变换是对偶图理论的应用，高中数学染色问题的图论解法和教务工作中期末考试安排和排课表问题是平面图的色数理论的应用。关键词：平面图，对偶图，色数，应用探究。The application of planar graph, dual graphs and chromatic numberXxxxxxxxxxxxxxx Class xxxx, Ma

3、thematics DepartmentTutor: xxxxxxxxAbstract: 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

4、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

5、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.1 引言图论起源于著名的哥尼斯堡七桥问题，欧拉在 1736 年解决了这个问题，并于 1753 年发现了欧拉公式而成为拓扑图论的奠基人。接着中断了 170 多年。1930 年，当波兰数学家 C.Kuratowski 和美国数

6、学家 O.Frink iFVvi(b) 对于图的面 和 的公共边界 , 有且仅有一条边 , 使得ij keEek, 且 与 相交;jikveke(c) 当且仅当 只是一个面 的边界时, 存在一个环 与 相交, 则称kiFivke是 的对偶图.G定义 2 若图 的对偶图 同构于 , 则称 是自对偶图.GG定理 1 设 是连通平面图 的对偶图, , , 和 , , 分别为 n*mrnr和 的顶点数、边数和面数, 则 (1) ; (2) ; (3) ; (4) 设Gr 的顶点 位于 的面 中, 则 .iviRiiRvdeg定理 2 设 是具有 个连通分支的平面图 的对偶图, 则(1) ;(2) wG

7、rn;(3) ;(4) 设 位于 的面 中, 则 , 其中m1nriViiiRVdeg, , , , , 同前.n*2.4 色数的相关概念和定理2.4.1 图中顶点的着色定义 1 图 的一种着色, 即对无环图 的每个顶点涂上一种颜色, 使相邻GG顶点涂不同的颜色.定义 2 对 进行 着色（ 是 可着色的）, 即能用 种颜色给 的顶GkkkG点着色.定义 3 的色数 , 即 是 可着色的, 但不是 可着色的.G1定理 1 当且仅当 为零图.定理 2 . nK定理 3 设 中至少含有一条边 , 则 当且仅当 为二部图.G2G定理 4 对于任意无向图 , 均有 . 1定理 5 圈图着色定理 : 用

8、( 为正整数) 种颜色给圈图 的顶点着色, 方knC法数为: , 其中 , .11, kfnnn 2nkf1定理 6 轮图着色定理: 用 ( 为正整数)种颜色给轮图 的顶点着色, 方knW法数为: ,其中 , , .)(2(,kgnn )(1kg2,1kfg推论 1 圈图 上一个指定的顶点染指定的颜色, 方法数为 , .nC推论 2 圈图 上两个指定相邻的顶点染指定的不同的颜色, 方法数为n, .)1(kfn2.4.2 边着色定义 1 对图 边的一种着色, 即对图 的每条边涂上一种颜色, 使相邻的GG边涂不同的颜色.定义 2 是 边可着色的, 即能用 种颜色给 的边着色.kk定义 3 的边色数

9、 , 即 是 边可着色的, 但不是 边可1k着色的, 也就是说最少用 种颜色给 的边着色.G定理 1 为简单平面图 , 则 .G1定理 2 若 是二部图, 则 . 2.4.3 面着色定义 1 是 面可着色的 , 即能用 种颜色给 的面着色, 就称对 的GkkGG面进行了 着色.定义 2 的面色数 , 即 是 面可着色的 , 但不是 面1k可着色的, 也就是说最少用 种颜色给 的面着色.k定理 1 图 是 面可着色的当且仅当它的对偶图 是 点可着色的.GG定理 2 任何平面图都是 可着色的. 53 平面图、对偶图和色数的应用3.1 平面图理论的应用例 1 (空调管道的设计) 某娱乐中心有 6 个景点, 位置分布如下图.图 10经考察知, 与 、 与 、 与 间人流较少 , 其它景点之间人流量大, 1A425A36必须投资铺设空调管道, 但要求空调管道间不能交叉. 如何设计?如果把每个景点分别模型为一个点, 景点间连线, 当且仅当两景点间要铺设空调管道. 那么, 上面问题直接对应的图为:图 11于是, 问题转化为, 能否把上图画在平面上, 使得边不会相互交叉?通过尝试, 可以把上图画为:图 12于是, 铺设方案为: