多边形三角化图三色问题证明的一个注记

山东大学学报(工学版)

多边形三角化图三色问题证明的一个注记

潘国栋，汪嘉业，向　辉

山东大学计算机科学与技术学院，山东济南 250061

收稿日期:2006-06-30 修回日期:1900-01-01 出版日期:2007-02-24 发布日期:2007-02-24
通讯作者: 潘国栋

A note on proof of the 3-Color problem of the polygon triangulation graph

PAN Guo-dong, WANG Jia-ye, XIANG Hui

School of Computer Science and Technology, Shandong University, Jinan 250061, China

Received:2006-06-30 Revised:1900-01-01 Online:2007-02-24 Published:2007-02-24
Contact: PAN Guo-dong

摘要/Abstract

摘要： 对“简单多边形三角形化图S是可以3色”的定理证明中用到的关键定理: “简单多边形三角形化图S的对偶图T是一棵树” 作了十分简化的证明, 从而简化了3色问题及Art Gallery 问题 Watchman 定理的证明.

关键词: k着色, 对偶图, 艺术馆走廊问题

Abstract: A brief proof to the key theory “The dual graph T of a simple polygon triangulation S is a tree" is given in the proof of theory “A simple polygon triangulation S is 3Color". Then it simplifies the proof of the 3Color problem and the Watchman Theory of Art Gallery Problem.

Key words: dual graph, Art Gallery Problem , kColor

中图分类号:

TP391

潘国栋,汪嘉业,向　辉 . 多边形三角化图三色问题证明的一个注记[J]. 山东大学学报(工学版), 2007, 37(1): 74-75 .

PAN Guo-dong,WANG Jia-ye,XIANG Hui . A note on proof of the 3-Color problem of the polygon triangulation graph[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(1): 74-75 .

参考文献

相关文章 15

[1]	熊冰妍, 王国胤, 邓维斌. 分级式代价敏感决策树及其在手机换机预测中的应用[J]. 山东大学学报(工学版), 2015, 45(5): 36-42.
[2]	王晓初, 王士同, 包芳. 基于概率密度分布一致约束的最小最大概率机图像分类算法[J]. 山东大学学报(工学版), 2015, 45(5): 13-21.
[3]	张东波,寇涛,许海霞. 基于LDB描述子和局部空间结构匹配的快速场景辨识[J]. 山东大学学报(工学版), 2018, 48(5): 16-23.
[4]	陈海永,余力,刘辉,杨佳博,胡启迪. 基于经验小波的太阳能电池缺陷图像融合[J]. 山东大学学报(工学版), 2018, 48(5): 24-31.
[5]	牟廉明. 自适应特征选择加权k子凸包分类[J]. 山东大学学报(工学版), 2018, 48(5): 32-37.
[6]	沈冬冬,周风余,栗梦媛,王淑倩,郭仁和. 基于集成深度神经网络的室内无线定位[J]. 山东大学学报(工学版), 2018, 48(5): 95-102.
[7]	张璞,刘畅,王永. 基于特征融合和集成学习的建议语句分类模型[J]. 山东大学学报(工学版), 2018, 48(5): 47-54.
[8]	王国新,陈凤东,刘国栋. 基于彩色伪随机编码结构光特征提取方法[J]. 山东大学学报(工学版), 2018, 48(5): 55-60.
[9]	胡建平,李鑫,谢琪,李玲,张道畅. 基于Delaunay三角化的二维无约束优化EMD方法[J]. 山东大学学报(工学版), 2018, 48(5): 9-15.
[10]	李广丽,刘斌,朱涛,殷依,张红斌. 基于优选典型相关分量的跨媒体检索模型[J]. 山东大学学报(工学版), 2018, 48(5): 38-46.
[11]	吴晨谋,方志军,黄正能. 基于单目摄像头的主动式驾驶行为分析算法[J]. 山东大学学报(工学版), 2018, 48(5): 69-76.
[12]	张宪红,张春蕊. 基于六维前馈神经网络模型的图像增强算法[J]. 山东大学学报(工学版), 2018, 48(4): 10-19.
[13]	江珊珊,杨静,范丽亚. 基于PDEs的图像特征提取方法[J]. 山东大学学报(工学版), 2018, 48(4): 27-36.
[14]	窦婷婷,姚元玺,陈鹏,芦灯. 基于ATP-EMTP的电弧建模及工程仿真[J]. 山东大学学报(工学版), 2018, 48(4): 102-108.
[15]	黄劲潮. 基于快速区域建议网络的图像多目标分割算法[J]. 山东大学学报(工学版), 2018, 48(4): 20-26.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed