| 多边形三角化图三色问题证明的一个注记 |
| |
| 引用本文： | 潘国栋,汪嘉业,向辉.多边形三角化图三色问题证明的一个注记[J].山东大学学报(工学版),2007,37(1):74-75. |
| |
| 作者姓名： | 潘国栋 汪嘉业 向辉 |
| |
| 作者单位： | 山东大学,计算机科学与技术学院,山东,济南,250061 |
| |
| 摘 要： | 对“简单多边形三角形化图S是可以3 色”的定理证明中用到的关键定理: “简单多边形三角形化图S的对偶图T是一棵树” 作了十分简化的证明, 从而简化了3 色问题及Art Gallery 问题 Watchman 定理的证明.
|
| 关 键 词： | k着色 对偶图 艺术馆走廊问题 |
| 文章编号： | 1672-3961(2007)01-0074-02 |
| 收稿时间： | 2006-06-30 |
| 修稿时间： | 2006年6月30日 |
A note on proof of the 3-Color problem of the polygon triangulation graph |
| |
| 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 of Technology,2007,37(1):74-75. |
| |
| Authors: | PAN Guo-dong WANG Jia-ye XIANG Hui |
| |
| Affiliation: | School of Computer Science and Technology, Shandong University, Jinan 250061, China |
| |
| 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. |
| |
| Keywords: | k-Color dual graph Art Gallery Problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(工学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(工学版)》下载全文 |
