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

山东大学学报(工学版)

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

潘国栋，汪嘉业，向　辉

山东大学计算机科学与技术学院，山东济南 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]. 山东大学学报 (工学版), 2025, 55(5): 62-69.
[2]	李二超, 张智钊. 在线动态订单需求车辆路径规划[J]. 山东大学学报 (工学版), 2024, 54(5): 62-73.
[3]	杨巨成, 魏峰, 林亮, 贾庆祥, 刘建征. 驾驶员疲劳驾驶检测研究综述[J]. 山东大学学报 (工学版), 2024, 54(2): 1-12.
[4]	肖伟, 郑更生, 陈钰佳. 结合自训练模型的命名实体识别方法[J]. 山东大学学报 (工学版), 2024, 54(2): 96-102.
[5]	胡钢, 王乐萌, 卢志宇, 王琴, 徐翔. 基于节点多阶邻居递阶关联贡献度的重要性辨识[J]. 山东大学学报 (工学版), 2024, 54(1): 1-10.
[6]	李家春,李博文,常建波. 一种高效且轻量的RGB单帧人脸反欺诈模型[J]. 山东大学学报 (工学版), 2023, 53(6): 1-7.
[7]	樊禹江,黄欢欢,丁佳雄,廖凯,余滨杉. 基于云模型的老旧小区韧性评价体系[J]. 山东大学学报 (工学版), 2023, 53(5): 1-9, 19.
[8]	李颖,王建坤. 基于监督图正则化和信息融合的轻度认知障碍分类方法[J]. 山东大学学报 (工学版), 2023, 53(4): 65-73.
[9]	吴艳丽,刘淑薇,何东晓,王晓宝,金弟. 刻画多种潜在关系的泊松-伽马主题模型[J]. 山东大学学报 (工学版), 2023, 53(2): 51-60.
[10]	余明骏,刁红军,凌兴宏. 基于轨迹掩膜的在线多目标跟踪方法[J]. 山东大学学报 (工学版), 2023, 53(2): 61-69.
[11]	刘行,杨璐,郝凡昌. 基于多特征融合的手指静脉图像检索方法[J]. 山东大学学报 (工学版), 2023, 53(2): 118-126.
[12]	刘方旭,王建,魏本征. 基于多空间注意力的小儿肺炎辅助诊断算法[J]. 山东大学学报 (工学版), 2023, 53(2): 135-142.
[13]	于艺旋,杨耕,耿华. 连续复合运动的多模态层次化关键帧提取方法[J]. 山东大学学报 (工学版), 2023, 53(2): 42-50.
[14]	黄华娟,程前,韦修喜,于楚楚. 融合Jaya高斯变异的自适应乌鸦搜索算法[J]. 山东大学学报 (工学版), 2023, 53(2): 11-22.
[15]	张豪,李子凌,刘通,张大伟,陶建华. 融合社会学因素的模糊贝叶斯网技术预测模型[J]. 山东大学学报 (工学版), 2023, 53(2): 23-33.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	孙从征,管从胜,秦敬玉,程川 . 铝合金化学镀镍磷合金结构和性能[J]. 山东大学学报(工学版), 2007, 37(5): 108 -112 .
[2]	刘新1 ，宋思利1 ，王新洪2 . 石墨配比对钨极氩弧熔敷层TiC增强相含量及分布形态的影响[J]. 山东大学学报(工学版), 2009, 39(2): 98 -100 .
[3]	陈朋胡文容裴海燕. 一株反硝化细菌LZ-14的筛选及其脱氮特性[J]. 山东大学学报(工学版), 2009, 39(5): 133 -138 .
[4]	郑洪亮,孔凡利, , 田学雷 . Al-Cu合金成分变化对其凝固潜热影响的研究[J]. 山东大学学报(工学版), 2008, 38(2): 10 -12 .
[5]	张宁李术才李明田杨磊. 新型岩石相似材料的研制[J]. 山东大学学报(工学版), 2009, 39(4): 149 -154 .
[6]	方挺,杨忠,沈春林 . 无人机编队视频序列中的多目标精确跟踪[J]. 山东大学学报(工学版), 2008, 38(4): 22 -26 .
[7]	王建平,王淑华,耿贵立 . InN半导体纳米晶相变活化能的研究[J]. 山东大学学报(工学版), 2008, 38(2): 42 -44 .
[8]	王秀红,郭庆强,李歧强 . 基于粒子群优化算法的高阶累积量滤波器[J]. 山东大学学报(工学版), 2007, 37(6): 15 -19 .
[9]	隋斌,朱维申,李树忱 . 岩锚吊车梁轮压作用下的三维稳定性分析[J]. 山东大学学报(工学版), 2008, 38(1): 80 -83 .
[10]	邱道宏1,张乐文1,崔伟2,苏茂鑫1,孙怀凤1. 基于趋势检查法的遗传神经网络模型及工程应用[J]. 山东大学学报(工学版), 2010, 40(3): 113 -118 .