极大平面图的结构与着色理论(2)多米诺构形与扩缩运算; Theory on Structure and Coloring of Maximal Planar Graphs (2) Domino Configurations and Extending-Contracting Operations | |
许进 | |
刊名 | 电子与信息学报
![]() |
2016 | |
关键词 | 极大平面图 扩缩运算 多米诺构形 祖先图 子孙图 递推构造法 Maximal planar graphs Extending-contracting operations Domino configurations Ancestor-graphs Descendent-graphs Recursive construction approach |
DOI | 10.11999/JEIT160224 |
英文摘要 | 业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征,本文提出一种构造极大平面图的方法扩缩运算。研究发现:此方法的关键问题是需要清楚一种构形,称为多米诺构形。文中构造性地给出了多米诺构形的充要条件;在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了:任一最小度4的(9)n -阶极大平面图必含(2)n -阶或(3)n -阶祖先图;给出极大平面图的递推构造法,并用此方法构造出6~12-阶所有最小度4的极大平面图。扩缩运算是本系列文章的基石。; The first paper of this series of articles revealed that Four-Color Conjecture is hopefully proved mathematically by investigating a special class of graphs, called the 4-chromatic-funnel, pseudo uniquely-4-colorable maximal planar graphs. To characterize the properties of such class of graphs, a novel technique,“extending-contracting operation”, is proposed which can be used to construct maximal planar graphs. The essence of this technique is to study a special kind of configurations, domino configurations. In this paper, a necessary and sufficient condition for a planar graph to be a domino configuration is constructively given, on the basis of which it is proposed to construct the ancestor-graphs and descendent-graphs of a graph. Particularly, it is proved that every maximal planar graph with order ( 9)n and minimum degree 4 has an ancestor-graph of order ( 2)n or ( 3)n . Moreover, an approach is put forward to construct maximal planar graphs recursively, by which all maximal planar graphs with order 6~12 and minimum degree 4 are constructed. The extending-contracting operation constitutes the foundation in this series of articles.; 国家973规划项目; 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)Foundation Items:The National 973 Program of China; The National Natural Science Foundation of China; EI; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 6; 1271-1296; 38 |
语种 | 中文 |
内容类型 | 期刊论文 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/493827] ![]() |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | 许进. 极大平面图的结构与着色理论(2)多米诺构形与扩缩运算, Theory on Structure and Coloring of Maximal Planar Graphs (2) Domino Configurations and Extending-Contracting Operations[J]. 电子与信息学报,2016. |
APA | 许进.(2016).极大平面图的结构与着色理论(2)多米诺构形与扩缩运算.电子与信息学报. |
MLA | 许进."极大平面图的结构与着色理论(2)多米诺构形与扩缩运算".电子与信息学报 (2016). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论