1. 交叉数研究进展
图的交叉数是图论中一个重要的部分,近百年来,国内外很多学者都对图的交叉数这一问题进行研究。图的交叉数问题的研究,起源于20世纪40年代砖厂遇到的难题。第二次世界大战时期,Turan [1] 发现运砖车沿铁轨向仓库运砖时,车很容易在铁轨交点的位置脱节。他因此想到通过减少铁轨交叉个数来降低损失的方法,交叉数的概念由此而来。Garey和Johnson [2] 证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大,国内外关于图的交叉数领域的研究进展缓慢。研究者们根据图的结构对图加以分类,取得了一些研究成果,下面主要介绍了完全图,完全二部图以及广义Petersen图的部分研究成果。
1.1. 完全图
1960年,R. K. Guy [3] 对n个顶点的完全图
的交叉数提出下面的猜想:
.
其中对任意实数x,
表示不超过x的最大整数。
1969年,R. K. Guy [4] 在文献中对完全图的交叉数进一步研究,验证了当
时,猜想成立。
1970年,Kieitman [5] 在文献中给出了当n足够大时,完全图
交叉数的下界:
2002年,Alcholzer,Aurenhammer和Krasserl [6] 用计算机穷举方法证明了
和
的交叉数分别是100和150,并给出了
的交叉数等于229。
1.2. 完全二部图
1954年,Zarankiewicz [7] 给出了完全二部图
交叉数的猜想:
.
1970年,Kieitman [5] 证明当
时,Zarankiewicz的猜想成立。
1993年,Woodall [8] 验证了Zarankiewicz的猜想对于
和
成立。
2003年,N. H. Nahas [9] 进一步研究当m,n足够大时完全二部图的交叉数:
.
1.3. 广义Petersen图
关于Petersen图的交叉数学者们进行了广泛的研究。最早研究广义Petersen图在1981年,Exoo,Harary和Kabel [10] 证明了:
1986年Fiorini [11] 对广义Petersen图的交叉数进行研究,计算出当
时所有
交叉数的具体值,然而Fiorini的证明存在错误。对于
给出了的数学证明,确定了
,并且
2002年,Richter和Salazar [12] 指出Fiorini的证明存在错误,用数学归纳法重新证明并更正了Fiorini的结论:
1997年Sarazin [13] 在其文章中证明了
。
Salazar [14] 给出了对于任意的
,
,有:
.
2004年,林晓惠 [15] 在其论文中得出了
等部分广义Petersen图的交叉数的上界。
2005年,马登举等人 [16] 证明了
的交叉数。
2009年,杨元生等人 [17] 利用算法给出了
时
的交叉数的精确值。
Fiorinil和黄元秋等人 [18] 分别用不同方法证明了
的交叉数。
2013年,郑百功 [19] 在硕士论文中证明了
的交叉数
2. 广义Petersen图P(4k,4)
设广义Petersen图
中的顶点集
,边集
,
,其中下标取模4k。设
,
和
,
且
,其中下标取模4k。很容易得到
是
的一个可传递分解,并且
是
的可传递一致2覆盖,其中
,即
.
画法D下的交叉数用
或
表示。设H是G的子图且
是H到所有非负实数集合的映射:
.
设
是G的一个可传递的一致k覆盖。假设
是
的并集,下标取模t,G中每一条边最多出现在
中的一个,否则设
表示多重图使
,
,对于
,uv恰好出现在
的
个子图中,
表示
中连接u和v的平行边数目,其中
。如果
是多重图,那么
.
设c是一个正整数。对于
,若存在一个正整数
满足
,则令
为
的最小值使
,若不存在这样的正整数
,则令
。
令
为圈
,
和
,
。对于路径P,如果
,则
表示P从u到v的连续顶点。
在本节中如果没有特别说明,假设i和k是正整数,当
时,设
且D为
的一个好画法,
。令
,
,由于
是
的一个细分,我们得到以下结果。
引理2.1
。
根据Jordan曲线定理,我们有以下引理。
引理2.2在图G中,设C和
为两个顶点不相交的圈,
为k阶路径且
。假设D是G的一个好画法,那么
是偶数;当
和
在
的同一区域时,
为偶数,否则为奇数。
为了后续证明叙述方便,现将引理2.2统称为引理2。
3. 广义Petersen图P(4k,4)的交叉数
引理3.1若
且
,则
,
,
和
都位于
划分的同一区域的同
一边界上。
证明:不失一般性,假设
和
。如果
和
不在
划分的同一区域的同一边界上,则由引理2可知,路径
和
交
,因此
,得出矛盾,则
和
在
划分的同一区域的同一边界上。如果
和
不在
划分的同一区域的同一边界上,则由引理2可知,路径
和
交
,因此
,得出矛盾,则
和
在
划分的同一区域的同一边界上。如果
和
不在
划分的同一区域的同一边界上,则由引理2可知,路径
和
交
,因此
,得出矛盾,则
和
在
划分的同一区域。因此
,
,
和
都位于
划分的同一区域的同一边界上。
若
且
,由引3.1,我们得到如下结果。
引理3.2若
且
,则
与图1中的其中一个图同构。
引理3.3若
且
,则
。
证明:不失一般性,假设
时
且
。通过
,得到
。由于
,由引理3.2和引理2得到
,因此
,得出矛盾。
引理3.4若
且
同构于图1(a),则
。
证明:反证法,不失一般性,假设
且
同构于图1(a)。通过
,得到
和
。由于
被交,由引理2.1可知在画法D下
和
是干净的。则在好的画法D下有
。由引理7得到
。
由
得到
。因此我们只需考虑以下情况:
情况1
。
情况2
。
引理3.5若
且
同构于图1(b),则
。
证明:反证法,不失一般性,假设
且
同构于图1(b)。通过
,得到
,
和
。由于
被交,由引理2.1可知在画法D下
和
都是干净的。因此
。由引理3.3得到
。由
得到
。因此我们考虑以下情况。
情况1
。
情况2
。
引理3.6若
且
同构于图1(c),则
。
证明:反证法,不失一般性,假设
且
同构于图1(c)。通过
,得到
,
和
。由于
被交,由引理4可知在画法D下
和
都是干净的。因此
。由引理7得到
。由
得到
。因此我们考虑以下情况。
情况1
。
情况2
。
引理3.7若
且
同构于图1(d),则
与图2同构,且
位于
或
区域,如图2所示。
证明:不失一般性,假设
且
同构于图1(d)。通过
,得到
,
,
和
。由于
和
被交,由引理2.1可知在画法D下
和
都是干净的。因此
。
由
得到
。由
,可知在画法D下
是干净的。由引理3.3得到
。当
时,
与图3(a),图3(b)和图3(c)中的一个图同构。
引理3.8若
,
与图2同构且
位于
区域,则
。
引理3.9若
,
与图2同构且
位于
区域,则
。
证明:反证法,不失一般性,假设
时
同构于图2且
在
中。通过
,得到
,
,
,
和
。由于
和
被交,由引理2.1可知在画法D下
和
都是干净的。由引理2以及
可知
。若
,由
可知
。
假设
且
。此时
与图4(a),图4(b)和图4(c)其中一个图同构。
假设
且
。此时
与图5(a),图5(b)和图5(c)其中一个图同构。
假设
。由
,得到
。此时
与图6(a),图6(b)和图6(c)其中一个图同构。
引理3.10若
且
同构于图1(e),则
。
证明:不失一般性,假设
且
同构于图1(e)。通过
,得到
,
和
。由于
和
被交,由引理2.1可知在画法D下
和
都是干净的。因此
。
引理3.11若
且
同构于图1(f),则
。
证明:反证法,不失一般性,假设
且
同构于图1(f)。通过
,得到
,
,
和
。由于
,可知在画法D下
是干净的。由引理7得到
。由
得到
。
当
时。由引理2可知有路径
交
。由
,得到
,且有路径
,
和
交
,与
相矛盾。因此
。由
得到
。因此我们考虑以下情况。
情况1
。
情况2
。
综上对于
且
时,总有
。
4. 结论
本文通过反证法和数学归纳法证明广义Petersen图
的交叉数,给出相应的好的画法,通过结合不同的计数公式和特殊的定义,对
的边进行分类,探究每组边上的交叉计数,最终验证关于图
在
且
时交叉数的下界至少等于2k,即
。