中国建筑师问题与对偶问题的4着色  

Problems of Chinese architects and dual of 4 colorings

作　　者：侴万禧[1] 班福志[2] 李晓毅[3] 刘畅 

机构地区：[1]安徽理工大学土木建筑学院,安徽淮南232001 [2]沈阳师范大学人事处,沈阳110034 [3]沈阳师范大学数学与系统科学学院,沈阳110034 [4]沈阳广全中学,沈阳110141

出　　处：《沈阳师范大学学报（自然科学版）》2012年第4期445-448,共4页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10471096;61070242)

摘　　要：提出了中国建筑师问题,阐明了求解中国建筑师问题的基本思路。介绍了25个顶点、69个边、45个面的对偶图的顶点4着色的全过程。将对偶图分解成含2棵可以2着色的对偶树的森林,在以r、b两色为对偶树得到的顶点实施2着色,以y、g两色为对偶树得到的顶点实施2着色,从而实施对偶图顶点的4着色。阐述了对偶图的4着色关键是将对偶图分解出森林,提出了3个森林的分解方法,讨论了H路径的个数、森林的个数、对偶图的A区和B区划分方案、对偶图的顶点4着色方案数。解决了对偶图顶点的4着色问题,利用对偶图顶点4着色方法使Kempe四色猜想"证明"中的漏洞得到了弥补。将此种方法用于12面体、20面体、22面体、32面体的对偶图的4色问题,并取得了成功。This paper proposes the Chinese architects＇ problems.It clarifies that the basic ideas in solving Chinese architecture problems,discovers method of forest decomposition for the dual graph with 4 top colorings,and gives 3 methods for forest decomposition.The whole process for 25 tops,69 edges,and 45 surfaces of dual graphs 4 top colorings are introduced.It discusses the numbers of H paths,the forests partition scheme for region A and region B,and the scheme numbers of dual graphs for 4 top colorings.The problems of dual graphs for 4 top colorings are solved.Use the methods of dual graphs for 4 top colorings,we can remedy the loophole of the proof for Kempe Guess of 4 colorings.It also succeed for solving 12 icosahedrons,20 icosahedrons,22 icosahedrons,and 32 icosahedrons of the problems with dual graphs 4 top colorings.It gives a new effective way in deal with dual graphs for spanning trees construction and count respect.

关 键 词：对偶图 4着色 森林 H路径 

分 类 号：O157[理学—数学]