循环图C(3m.m)的交叉数的新证明
设V(G)和E(G)分别是图G的点集和边集，图画在平面上是指将图的顶点集中各点映射到平面上的不同的点，然后将边集的每一条边(u, v)映射为平面上的一条连续的线上使得该线的端点恰好是顶点u和v的象。如果画法满足以下几条:(1)任何两条边最多相交一次;(2)边自身不相交;(3)有相同端点的两条边不相交:(4)没有三条边交于同一个点;(5)任何一边不过除它端点之外的顶点，则称该画法为图G的好画法。图G的交叉数是指在G的所有好的画法中边交叉点最少的个数，记为cr(G)。满足交叉点个数最少的画法称为图G的最优画法。本文运用计算边交叉的次数和归纳的方法,得出了循环图C(3m.m)m≥3的交叉数是m。
循环图 交叉数 最优画法 边交叉点
刘晶波 郝荣霞 张建根
中央民族大学数学系,北京 100081 北京交通大学数学系,北京 100081 北京交通大学数学系,北京 100081 北京理工大学计算机科学技术学院,北京 100081
国内会议
南京
中文
243-246
2008-10-18（万方平台首次上网日期，不代表论文的发表时间）