论文部分内容阅读
图的交叉数是衡量图的非平面性的一个重要参数,Garey和Johnson证明了计算图的交叉数问题是NP完全的。目前仅确定了少数几类图的交叉数。完全图,完全二分图,广义Petersen图,循环图,顶点数较小的图与路径、圈或者星图的交图是交叉数问题中活跃的研究对象。 Kn(?)del图是一种互连网络,研究互连网络的交叉数有助于更好地理解其拓扑性质。本文研究了Kn(?)del图W3,n(n≥8,n为偶数)的交叉数。首先利用计算机构造了W3,n交叉数较少的画法,给出交叉数上界;然后设计了W3,n的边分组方式和交叉点计数函数给出其下界。最终证明: cr(W3,8)=0;cr(W3,10)=1;cr(W3,n)=[n/6]+n mod 6/2,当n≥12时。 Ringeisen和Beineke给出了K3□Cn以及K4□Cn的交叉数。本文进一步研究了完全图和圈的交图Km□Cn的交叉数。通过设计Km□Cn的分组方式和交叉点计数方法,给出了Km□Cn交叉数的下界: cr(Km□Cn)≥n cr(Km+2)。通过改进计算图的交叉数算法CCN的限界条件,利用计算机构造了Km□Cn好的画法,给出了Km□Cn交叉数的上界: cr(Km□Cn)≤n/4[m+2/2][m+1/2][2/2][m-1/2](n为偶数); cr(Km□Cn)≤n/4[m+2/2][m+1/2][m/2][m-1/2]+[m-1/2]2(n为奇数)。因为m≤12时Guy给出的完全图交叉数猜想成立,所以当m≤10,n为偶数时,有: cr(Km□Cn)=n/4[m+2/2][m+1/2][m/2][m-1/2](m≤10且n为偶数)。当n为奇数时,利用计算机构造出了K5□Cn,K6□Cn和K7口Cn的交叉数更少的画法,进一步改进了上界。从而完全确定了这三类图的交叉数: cr(K5□Cn)=9n;cr(K6□Cn)=18n;cr(K7□Cn)=36n。