关于一类以正常着色图为顶点的图的研究
摘要：本文从基础图出发，对给定的着色数，讨论以基础图的所有正常着色图作为顶点，并将其中有且仅有一点异色的正常着色图相连构成其边集而形成的被称为的图所具有的性质。本文尝试寻找的构成规律，对于给定的顶点数以及着色数，研究某些特定类型的图生成的所具有的结构。特别是对散点图和线形图的情况，其生成的具有一定的规律性，本文对这些规律进行了统一的描述，并给出了理论证明。同时，本文还遵循从简单到复杂的方式对其它各类图生成的所具有的性质进行了研究。在上述工作的基础上，本文还给出了在顶点数有限的条件下寻找构成已知的的图与着色数的算法，并通过Matlab完成了其中部分程序的设计。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1 绪论2
1.1 图论的历史及应用2
1.2 本文研究的问题3
2基础知识4
2.1基本概念4
2.2相关定理介绍5
3 由给定的图与着色数生成的5
3.1 为散点图 5
3.1.1 的情况5
3.1.2 的情况5
3.1.3 的情况 5
3.2 为线形图8
3.2.1 的情况8
3.2.2 的情况8
3.3 为环形图8
3.3.1 的情况8
3.3.2 的情况8
3.4 为完全图9
4任给有限定地给出以此为的图与着色数9
4.1 基本原理9
4.2 算法实现9
4.2.1 步骤一的算法9
4.2.2 步骤二的算法10
5 总结10
5.1 本文的创新之处10
5.2 进一步的研究方向10
致谢10
参考文献11
附录 代码11
关于一类以正常着色图为顶点的图的研究
引言
引言
对于图论的研究始于十八世纪早期欧拉提出的“七桥问题”，尽管这在
*好棒文|www.hbsrm.com +Q: 3_5_1_9_1_6_0_7_2
当时引起了广泛的热议，但是之后却被视为无足轻重的研究[1]。直到在十九世纪中叶，德摩根提出著名的“四色问题”时，人们才再一次关注图论这个领域，当然在此期间图论也悄然引起了一批研究者的兴趣并得到了一定程度的重视。尽管目前人们对图论的研究已经取得了卓越的成果，但其中仍有许多全新的领域有待探索[2, 3, 5, 7, 8, 12]。本文将研究一种具有独特性质的图，记为。这种图的生成方式是从给定的图出发，通过对其顶点进行着色从而得到若干正常着色图，并依据特定规则将这些正常着色图作为顶点进行连结而得到的图。本文将给出这类图的定义及特征，并尝试分析此类图的构成规律[3]。
绪论
1．1 图论的历史及应用
图论是属于应用数学的一个分支，虽然很多数学家都曾独立地构建过自己的类似于图论的相关理论，但是对图论进行较为完整的记述要追溯到公元1736年由瑞士数学家欧拉撰写的关于哥尼斯堡七桥问题的论文[1, 6, 9]。
哥尼斯堡是公元18世纪位于东普鲁士的一个城市，这个城市的陆地被普格莱河分割成了两岸及两个河心岛四个部分。这四块陆地之间由七座桥相连，如图1中的a)所示。所谓的七桥问题就是从任何一块陆地出发，能否不重不漏地遍历所有的桥，并回到出发点。后来欧拉将这个实际问题抽象为图1中的b)所示的图论问题，即问在四个顶点间是否存在一条能够不重不漏地遍历所有边的回路[5, 6]。
图1
后来欧拉在文章中证明了这个问题是没有解的，并且还对这个问题进行了推广。通过给出对于一个给定的图是否能以某种方式遍历的判定法则成为了图论及拓扑学的奠基人之一。
图论发展历程的第二阶段是从公元19世纪中叶到1936年。在1878年，图（Graph）作为一个学术专有词第一次出现在英国的《自然》杂志上。在这个阶段，大量的图论问题被提出，著名的如1852年提出的四色问题、1856年提出的Hamilton问题等等。与此同时，以图为工具来解决其他领域的问题的做法也获得了许多辉煌的成绩，比如克西霍夫在1847年为了解一类线性方程组而发展的树的理论，这个线性方程组是用来描述一个电网络的每一条支路和环绕每一个回路的电流，通过将一个电网络和其中的电阻、电容、电感等等抽象化成由点和线组成的相应组合结构，他实际上用基本图代替了电网。另一个著名的案例是凯莱利用树的概念对有机化学的分子结构问题进行的研究。进入二十世纪三十年代后，图论得到了进一步发展，比如1927年提出的Menger定理，1930年提出的Kuratowski定理以及同年提出的Ramsey定理等等。这些理论和结果为图论成为一个重要的数学分支奠定了坚实的基础[7]。而匈牙利数学家D.Konig在1936年写出的《有限图与无限图的理论》作为第一本图论专著，标志着图论正式成为了一个数学分支。
1936年至今是图论发展的第三阶段，在这个阶段，在生产管理、交通运输、网络通讯等各个方面提出的一系列问题[8]，尤其是许多离散性问题的出现大大推动了图论的发展。比如在公元二十世纪五十年代，Mason发表的信号流图研究反馈系统理论与Seshu、Busarer、Chen等人对之前克西霍夫提出的电网络理论的总结与发展。进入七十年代以后，电子计算机的出现使得图论得到进一步发展，比如Whitney, Tutte, Haray等人对一般图论与拓扑学的发展、Biggs等人对代数论的发展及其在化学领域的应用、Berge等人推广出的超图等等[14]。
现在图论已然成为全世界数学领域的重点研究对象之一，就其本身而言，也有最初的七桥问题发展成了具有代数图论、拓扑图论、随机图论、计数图论、算法图论、无限图论等多个分支多个学派的现代数学学科。
图论是一门将事物抽象为点、将联系抽象为线，并借由其特性进行研究的学科。事实上图论自奠基之初就是为了解决七桥问题，因此图论是一门极具应用性的学科。图论作为组合数学与离散数学的重要分支[10, 11]，在自然科学、经济管理与社会科学的研究中已经是一项重要的数学工具了。
图论的应用极为广泛，比如在运筹学领域[10, 13]，Ford和Fulkerson研究出的网络流问题标号法。此外图论和数学的其他分支如群论等也有着密切联系，事实上，图论可以为任何一个至少包含一种二元关系的系统提出一个数学模型[1]。
1．2 本文研究的问题
着色图是一种给顶点分配颜色的图，而正常着色图则是在着色图的基础上要求相邻点异色。图的着色在运筹学领域有着诸多应用，例如对于变址寄存器的设计或是频道的安排等。
给定图以及着色数，由此生成的图被称为，如果它是一个以所有满足正常着色的图为顶点，并将有且仅有一点异色的图相连而形成的图。其中，的正常着色图中必须使用全部种颜色。
对于给定的图以及着色数，考虑由此生成的所有正常着色图及相应的图所具有的性质，以及对给定的图又该怎样判断它是否满足作为的条件，如果满足则相应的图与着色数又是怎样的。研究这些问题如果仅仅依赖纸和笔显然是一项艰苦的工作，所以本文借助研究二值化图像识别的思想和方法，将所研究的无向图转化为二维矩阵，并通过编写Matlab程序来对这些矩阵进行研究。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1 绪论2
1.1 图论的历史及应用2
1.2 本文研究的问题3
2基础知识4
2.1基本概念4
2.2相关定理介绍5
3 由给定的图与着色数生成的5
3.1 为散点图 5
3.1.1 的情况5
3.1.2 的情况5
3.1.3 的情况 5
3.2 为线形图8
3.2.1 的情况8
3.2.2 的情况8
3.3 为环形图8
3.3.1 的情况8
3.3.2 的情况8
3.4 为完全图9
4任给有限定地给出以此为的图与着色数9
4.1 基本原理9
4.2 算法实现9
4.2.1 步骤一的算法9
4.2.2 步骤二的算法10
5 总结10
5.1 本文的创新之处10
5.2 进一步的研究方向10
致谢10
参考文献11
附录 代码11
关于一类以正常着色图为顶点的图的研究
引言
引言
对于图论的研究始于十八世纪早期欧拉提出的“七桥问题”，尽管这在
*好棒文|www.hbsrm.com +Q: 3_5_1_9_1_6_0_7_2
当时引起了广泛的热议，但是之后却被视为无足轻重的研究[1]。直到在十九世纪中叶，德摩根提出著名的“四色问题”时，人们才再一次关注图论这个领域，当然在此期间图论也悄然引起了一批研究者的兴趣并得到了一定程度的重视。尽管目前人们对图论的研究已经取得了卓越的成果，但其中仍有许多全新的领域有待探索[2, 3, 5, 7, 8, 12]。本文将研究一种具有独特性质的图，记为。这种图的生成方式是从给定的图出发，通过对其顶点进行着色从而得到若干正常着色图，并依据特定规则将这些正常着色图作为顶点进行连结而得到的图。本文将给出这类图的定义及特征，并尝试分析此类图的构成规律[3]。
绪论
1．1 图论的历史及应用
图论是属于应用数学的一个分支，虽然很多数学家都曾独立地构建过自己的类似于图论的相关理论，但是对图论进行较为完整的记述要追溯到公元1736年由瑞士数学家欧拉撰写的关于哥尼斯堡七桥问题的论文[1, 6, 9]。
哥尼斯堡是公元18世纪位于东普鲁士的一个城市，这个城市的陆地被普格莱河分割成了两岸及两个河心岛四个部分。这四块陆地之间由七座桥相连，如图1中的a)所示。所谓的七桥问题就是从任何一块陆地出发，能否不重不漏地遍历所有的桥，并回到出发点。后来欧拉将这个实际问题抽象为图1中的b)所示的图论问题，即问在四个顶点间是否存在一条能够不重不漏地遍历所有边的回路[5, 6]。
图1
后来欧拉在文章中证明了这个问题是没有解的，并且还对这个问题进行了推广。通过给出对于一个给定的图是否能以某种方式遍历的判定法则成为了图论及拓扑学的奠基人之一。
图论发展历程的第二阶段是从公元19世纪中叶到1936年。在1878年，图（Graph）作为一个学术专有词第一次出现在英国的《自然》杂志上。在这个阶段，大量的图论问题被提出，著名的如1852年提出的四色问题、1856年提出的Hamilton问题等等。与此同时，以图为工具来解决其他领域的问题的做法也获得了许多辉煌的成绩，比如克西霍夫在1847年为了解一类线性方程组而发展的树的理论，这个线性方程组是用来描述一个电网络的每一条支路和环绕每一个回路的电流，通过将一个电网络和其中的电阻、电容、电感等等抽象化成由点和线组成的相应组合结构，他实际上用基本图代替了电网。另一个著名的案例是凯莱利用树的概念对有机化学的分子结构问题进行的研究。进入二十世纪三十年代后，图论得到了进一步发展，比如1927年提出的Menger定理，1930年提出的Kuratowski定理以及同年提出的Ramsey定理等等。这些理论和结果为图论成为一个重要的数学分支奠定了坚实的基础[7]。而匈牙利数学家D.Konig在1936年写出的《有限图与无限图的理论》作为第一本图论专著，标志着图论正式成为了一个数学分支。
1936年至今是图论发展的第三阶段，在这个阶段，在生产管理、交通运输、网络通讯等各个方面提出的一系列问题[8]，尤其是许多离散性问题的出现大大推动了图论的发展。比如在公元二十世纪五十年代，Mason发表的信号流图研究反馈系统理论与Seshu、Busarer、Chen等人对之前克西霍夫提出的电网络理论的总结与发展。进入七十年代以后，电子计算机的出现使得图论得到进一步发展，比如Whitney, Tutte, Haray等人对一般图论与拓扑学的发展、Biggs等人对代数论的发展及其在化学领域的应用、Berge等人推广出的超图等等[14]。
现在图论已然成为全世界数学领域的重点研究对象之一，就其本身而言，也有最初的七桥问题发展成了具有代数图论、拓扑图论、随机图论、计数图论、算法图论、无限图论等多个分支多个学派的现代数学学科。
图论是一门将事物抽象为点、将联系抽象为线，并借由其特性进行研究的学科。事实上图论自奠基之初就是为了解决七桥问题，因此图论是一门极具应用性的学科。图论作为组合数学与离散数学的重要分支[10, 11]，在自然科学、经济管理与社会科学的研究中已经是一项重要的数学工具了。
图论的应用极为广泛，比如在运筹学领域[10, 13]，Ford和Fulkerson研究出的网络流问题标号法。此外图论和数学的其他分支如群论等也有着密切联系，事实上，图论可以为任何一个至少包含一种二元关系的系统提出一个数学模型[1]。
1．2 本文研究的问题
着色图是一种给顶点分配颜色的图，而正常着色图则是在着色图的基础上要求相邻点异色。图的着色在运筹学领域有着诸多应用，例如对于变址寄存器的设计或是频道的安排等。
给定图以及着色数，由此生成的图被称为，如果它是一个以所有满足正常着色的图为顶点，并将有且仅有一点异色的图相连而形成的图。其中，的正常着色图中必须使用全部种颜色。
对于给定的图以及着色数，考虑由此生成的所有正常着色图及相应的图所具有的性质，以及对给定的图又该怎样判断它是否满足作为的条件，如果满足则相应的图与着色数又是怎样的。研究这些问题如果仅仅依赖纸和笔显然是一项艰苦的工作，所以本文借助研究二值化图像识别的思想和方法，将所研究的无向图转化为二维矩阵，并通过编写Matlab程序来对这些矩阵进行研究。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/xxaq/978.html
