论文部分内容阅读
图的交叉数问题是在实际应用中提出来的,在电子线路板的设计,CAD领域有广阔的应用。目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图。本文对一些顶点数较大或交叉数较大的图的交叉数问题进行研究,将计算机构造性证明和数学证明相结合,取得了较好的结果。本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数。但由于图的交叉数问题是NP困难问题,对顶点数较大或交叉数较大的图,所需要的计算时间仍然太多。针对这一问题,本文给出了计算图的交叉数上界的算法CCN*,把计算图的交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问题,从而可以对较大规模的图的交叉数性质进行研究。利用该算法计算了顶点数p≤12的所有路径幂图Pnk和13≤p≤20且k≤9的所有Pnk的较好的交叉数上界。对与圈Cn交图的交叉数,目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数。Ringeisen和Beineke对Km□Cn,m≤4进行了研究。本文对Km□Cn进行研究,给出了相应的交叉数计数方法,确定了这类图的交叉数下界。对m=5,6,7或者n为不小于4的偶数,给出了交叉数上界及对应的画法;如果著名的完全图交叉数猜想对Km+2成立,则本文给出的交叉数上界就是完全图Km与圈Cn交图的交叉数。对与路径Pn交图的交叉数,目前研究的较多的也是顶点数较小的图与路径交图的交叉数。Kle(?)等人对Km□Pn,m≤5进行了研究。Bokal对K1,l□Pn进行了研究。黄元秋与Kle(?)分别研究了Wm□Pn的n≤3与m=3,4的情形;Kle(?)对W2,3□Pn进行了研究。本文针对Km□Pn,Km,l□Pn,Wl,m□Pn进行了研究,给出了这些图的交叉数上界。并对其中Km□Pn,K2,l□Pn,Wm□Pn,W2,m□Pn给出了相应的交叉数计数方法,进而导出了这些图的交叉数下界。并最终确定了K6□Pn,K2,l□Pn,Wm□Pn,W2,m□Pn的交叉数,扩展了与路径交图的交叉数的研究结果。本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题。作为应用实例,本文确定了两类三正则图Kn(?)del图J3,n和Flower Snark及其相关图Fn的交叉数。相信该方法在图的交叉数问题研究中还有更广泛的应用。