四色图论——四色问题解的存在性及求解方法 被引量：2

1

作者 杨名生 《大连理工大学学报》 EI CAS CSCD 北大核心 2016年第6期662-670,共9页

直接从四色问题出发,建立图论的另外一个新体系.在提出区域、边界线、结点等定义,对复杂地图进行分层简化后,得到体系的3个基本定理,又用链路这一工具,证明任意有限个区域地图的四色解存在并给出了求解方法.

关键词 图论 四色问题 区域 边界线 结点 链路

下载PDF 职称材料

对若干“历史性”问题的讨论——信息的本质、四色问题、康托对角线法、芝诺悖论、麦克斯韦妖的再认识 被引量：1

2

作者 沈卫国 《天津职业院校联合学报》 2009年第6期99-107,共9页

针对标题所列"历史性"科学问题,结合以往有关学术思想,提出、补充若干新的视角、观点、证明等,以使这些问题的解决更加明确和易于理解。

关键词 信息 四色问题 康托对角线法 芝诺悖论 麦克斯韦妖

下载PDF 职称材料

关于非平面图染色的一个猜想 被引量：1

3

作者 张祥波 《山东科学》 CAS 2017年第3期94-97,共4页

本文提出以下猜想:若θ(G)=2,则χ(G)≤9;若θ(G)≥3,则χ(G)≤6θ(G)-1。证明了当 |S|∈{p,p-1,p-2,p-3,p-4,p-5}时,该猜想是正确的。

关键词 四色问题 顶点染色数 图的厚度 平面图

下载PDF 职称材料

极大平面图中二色树子图的一个必要条件

4

作者 许寿椿 《中央民族大学学报（自然科学版）》 2005年第3期206-208,共3页

极大平面图G=(V,E)中的一个二色树子图T=(Vt,Et),其Vt在G中导出子图为树,并且图G存在至少一个四着色C,使T是该四着色一个二色子图的一个连通支.本文证明了Vt的点次和为偶数是它成为二色树子图的必要条件.

关键词 极大平面图 四色问题 二色子图

下载PDF 职称材料

模拟退火算法思想在求解四色问题中的应用

5

作者 黄仁帅 《科技创新与应用》 2018年第24期164-165,共2页

四色问题又称四色猜想,是世界近代三大数学难题之一。对四色问题的研究,促进了一系列数学新思维的产生,为推动数学的发展起到了重要的作用。模拟退火算法是求解复杂工程问题的重要算法之一。文章基于模拟退火算法的思想,结合四色问题的... 四色问题又称四色猜想,是世界近代三大数学难题之一。对四色问题的研究,促进了一系列数学新思维的产生,为推动数学的发展起到了重要的作用。模拟退火算法是求解复杂工程问题的重要算法之一。文章基于模拟退火算法的思想,结合四色问题的特殊性,给出了一种求解四色问题的快速算法。 展开更多

关键词 模拟退火 四色问题 智能算法

下载PDF 职称材料

地图自动着色算法研究与实践

6

作者 李晓年 张国合 +1 位作者 朱翊 刘晓东 《地理信息世界》 2011年第6期53-56,59,共5页

从四色问题的抽象模型入手,通过对现有的搜索算法——遗传算法、模拟退火算法这两种算法的原理和流程进行了较为细致的分析,总结出它们在地图四色填充实现过程中的优点与不足之处,并进行比较,找出这两种算法的结合点进行算法的改进优化... 从四色问题的抽象模型入手,通过对现有的搜索算法——遗传算法、模拟退火算法这两种算法的原理和流程进行了较为细致的分析,总结出它们在地图四色填充实现过程中的优点与不足之处,并进行比较,找出这两种算法的结合点进行算法的改进优化,将模拟退火算法引入遗传算法,使它们结合起来解决地图四色填充问题,从而形成相对优化的算法,以期达到更加优化的效果。 展开更多

关键词 四色定理 遗传算法 模拟退火算法 适应度 METROPOLIS准则

下载PDF 职称材料

极大平面图的局部结构及其着色特性 被引量：6

7

作者 许寿椿 《中央民族大学学报（自然科学版）》 1994年第2期6-14,共9页

本文在文献［１］的基础上，进一步研究了极大平面图层圈结构中的几种典型局部结构及着色特性。这些局部结构包括轮图（由点ｖ及Ｄ１（ｖ）生成），弦弧圈（由Ｄｒ（ｖ）生成），圈村图（由Ｄｒ－１与Ｄｒ生成）及平行圈和层间结构（由... 本文在文献［１］的基础上，进一步研究了极大平面图层圈结构中的几种典型局部结构及着色特性。这些局部结构包括轮图（由点ｖ及Ｄ１（ｖ）生成），弦弧圈（由Ｄｒ（ｖ）生成），圈村图（由Ｄｒ－１与Ｄｒ生成）及平行圈和层间结构（由Ｄｉ与Ｄｉ＋１生成）。这些结构的多数可以简单地确定具有３色性或４色性。最后，讨论了任意极大平面图表示为两个典型局部结构的某种二元分解问题。 展开更多

关键词 极大平面图 四色问题 着色 层圈结构

下载PDF 职称材料

一个实用的地图着色算法 被引量：5

8

作者 毛云舟 《江苏师范大学学报（自然科学版）》 1998年第4期19-20,共2页

给出一种计算机实现地图四色着色的算法，并以Ｐａｓｃａｌ语言编制了程序．该程序稍作改动，即可成为分块图形实现四色着色的通用程序．

关键词 地图 四色问题 算法

下载PDF 职称材料

组合数学浅析 被引量：1

9

作者 胡勤 《电脑知识与技术（过刊）》 2010年第13期2801-2802,共2页

该文介绍了组合数学的定义及研究内容,组合数学的经典问题及组合数学在日常生产、生活和计算机科学中的广泛应用和重要意义。

关键词 组合数学 四色问题 邮差问题

全文增补中

小议数学发展的哲学问题及其在数学与计算机科学关系中的表现 被引量：1

10

作者 孙宏涛 《数学的实践与认识》 CSCD 北大核心 2003年第1期101-110,共10页

本文从哲学角度讨论数学与实践的联系 ,并以数学与计算机科学的关系为例说明这种联系 .

关键词 变分学 偏微分方程理论 悖论 毕达哥拉斯定理 康托集合论 相容性 矩阵理论 黎曼几何 群论 数学 哲学

原文传递

两个只有路型二色子图的极大平面图 被引量：1

11

作者 许寿椿 《中央民族大学学报（自然科学版）》 2005年第1期5-9,共5页

　本文证明了极大平面图g9D和g12A,其每个四着色的每个二色子图都是路.并猜测在全部无分离三圈的极大平面图中这是仅有的两个图.

关键词 四色问题 四着色算法 极大平面图 二色子图 色多项式

下载PDF 职称材料

基于C语言的GIS地图着色问题的实现 被引量：1

12

作者 郭仁安 郭先春 《城市勘测》 2012年第6期121-123,共3页

首先论述了地理信息系统的发展,重点讨论了其中的地图着色问题,并结合数据结构中的"贪心算法"用C语言编程,完成了英国人格思里于1852年提出任何一种地图只需要4种颜色就能表达的问题,即四色问题,最后展示了实现的结果。

关键词 地理信息系统 数据结构 四色问题 贪心算法

下载PDF 职称材料

平面三次图哈米尔顿性的一个充要条件 被引量：1

13

作者 许寿椿 《中央民族大学学报（自然科学版）》 2008年第3期11-16,共6页

本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色.即Dg的对偶极大平面图g有四着色C,该四着色的某组对偶二色子图Gk的两个分支都是树.据此得到求出图Dg全部哈米尔顿圈的算法,该方法已经成功处理... 本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色.即Dg的对偶极大平面图g有四着色C,该四着色的某组对偶二色子图Gk的两个分支都是树.据此得到求出图Dg全部哈米尔顿圈的算法,该方法已经成功处理了批量例图. 展开更多

关键词 四色问题 极大平面图 平面三正则图 哈米尔顿圈

下载PDF 职称材料

用遗传算法实现四色图问题 被引量：1

14

作者 火善栋 《计算机时代》 2015年第3期56-57,60,共3页

遗传算法是模拟生物进化过程的算法,任何问题只要能用一组合适的编码来表示其中的一个可行解,那么这个可行解就可以看做是一个生物个体,若干个可行解就可以看做是一个生物种群。将问题的若干个可行解利用生物进化的特点,最终就可以简单... 遗传算法是模拟生物进化过程的算法,任何问题只要能用一组合适的编码来表示其中的一个可行解,那么这个可行解就可以看做是一个生物个体,若干个可行解就可以看做是一个生物种群。将问题的若干个可行解利用生物进化的特点,最终就可以简单快速地得到问题的一个最优解。利用遗传算法和四色图问题的这一特点,通过遗传算法实现了四色图问题的求解。实验证明,用遗传算法实现类似的四色图问题,思想简单,收敛速度快。 展开更多

关键词 四色图问题 遗传算法 染色体编码 邻接矩阵

下载PDF 职称材料

关于四色问题的P.J.Heawood反例

15

作者 叶凤常 《贵州科学》 1999年第3期161-164,共4页

英国数学家Kampe给出了四色定律的第一个证明，10年后Heawood指出该证明有致命错误，Heawood还利用Kampe的方法证明了五色定理．本文分析了Kampe方法的漏洞，同时也分析了Kampe方法的潜在威力，为此，引入“Kampe链”的概念，并把它用... 英国数学家Kampe给出了四色定律的第一个证明，10年后Heawood指出该证明有致命错误，Heawood还利用Kampe的方法证明了五色定理．本文分析了Kampe方法的漏洞，同时也分析了Kampe方法的潜在威力，为此，引入“Kampe链”的概念，并把它用到四色问题的几类特殊情况的证明．简化了Heawood的反例，分析了反例的逻辑结构． 展开更多

关键词 肯普链 希伍德反例 平面图 着色 四色定理

下载PDF 职称材料

平面三次图中的二元哈米顿圈

16

作者 许寿椿 《中央民族大学学报（自然科学版）》 2009年第1期34-38,46,共6页

本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=R∪S,其中R连通... 本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=R∪S,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图. 展开更多

关键词 四色问题 极大平面图 平面三正则图 哈米顿圈 二元哈米顿圈

下载PDF 职称材料

研究四色问题的意义及理论构想 被引量：6

17

作者 张祥波 《数学理论与应用》 2012年第3期24-28,共5页

四色问题又称四色猜想,是世界近代三大数学难题之一.1976年两位美国数学家Appel与Haken借助计算机给出了一个证明.时至今日,四色问题的正确性早已得到数学界所承认.但是围绕它的非计算机证明,在近几十年来涌现出了各种不同的研究成果.... 四色问题又称四色猜想,是世界近代三大数学难题之一.1976年两位美国数学家Appel与Haken借助计算机给出了一个证明.时至今日,四色问题的正确性早已得到数学界所承认.但是围绕它的非计算机证明,在近几十年来涌现出了各种不同的研究成果.一方面丰富了图论的内容,另一方面又促进了图的染色理论的发展.本文从研究四色问题的意义出发;揭示了四色问题所隐藏的深刻规律,在此基础上提出了一个比四色问题更具有广泛意义的理论构想.主要目地为四色问题的非计算机证明提供一个研究方向. 展开更多

关键词 四色问题、非计算机证明、图的色数、图的厚度

下载PDF 职称材料

整数流与子图覆盖 被引量：3

18

作者 范更华 《中国科学：数学》 CSCD 北大核心 2017年第4期457-466,共10页

整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函... 整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函数值之和等于离开该点的边函数值之和.整数流理论与数学其他领域一些著名问题有一定的关联,如组合学的孤独跑步者、数论的丢番图逼近、几何学的视线阻碍和线性空间堆垒基等.四色问题还等价于平面图的偶子图覆盖问题:是否存在3个偶子图,覆盖一个2-边连通平面图的每条边恰好两次.著名的Fulkerson猜想认为,对每个2-边连通图(不必是平面图),存在6个偶子图,覆盖该图的每条边恰好4次.本文对整数流和子图覆盖这两个研究方向及相关问题的历史和现状作一个综述. 展开更多

关键词 整数流 子图覆盖 四色问题 EULER图 圈路覆盖

原文传递