摘要:业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征,本文提出一种构造极大平面图的方法——扩缩运算。研究发现:此方法的关键问题是需要清楚一种构形,称为多米诺构形。文中构造性地给出了多米诺构形的充要条件;在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了:任一最小度≥4的n(≥9)-阶极大平面图必含(n-2)-阶或(n-3)-阶祖先图;给出极大平面图的递推构造法,并用此方法构造出6~12-阶所有最小度≥4的极大平面图。扩缩运算是本系列文章的基石。
关键词:极大平面图 扩缩运算 多米诺构形 祖先图 子孙图
单位:北京大学高可信软件技术教育部重点实验室; 北京100871; 北京大学信息科学技术学院; 北京100871
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社