【作者】 郑文萍；

【导师】 杨元生；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2007， 博士

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

【Abstract】 Crossing numbers of graphs are in general very difficult to compute. The exact crossing numbers of very few families of graphs are known. Using computer algorithm to compute upper bounds, and using mathmatical techniques to get lower bounds, this thesis researches on the crossing numbers of some graphs with relative large order or with relative large crossing number.The exist algorithm CCN proposed in 2002 computes the crossing numbers of all the graphs with some order. Unfortunately, the crossing number of a graph is NP complete, and not much hope is held for efficiently finding all optimal drawings-or even a single optimal drawing-for all graphs. An algorithm CCN^* is presented in the thesis to compute upper bounds of the crossing number of path power graphs P_n^k. Let p=|V（G）|. The upper bounds of crossing numbers of P_n^k where p≤12 or 13≤p≤20 with k≤9 are computed by CCN^*.Then we investigate the Crossing number of Cartesian products with cycles and paths. For the Cartesian product of cycle and complete graph, Ringeisen and Beineke have proved that cr（C₃□C_n）=n and cr（K₄□C_n）=3n. The thesis obtains a lower bound for K_m□C_n using a special crossing counting method for K_m□C_n, i.e. cr（K_m□C_n）≥n×cr(K_m+2) for n≥3 and m≥5. It is also proved that, cr（K_m□C_n）≤n/4（?）（m+2）/2」（?）（m+1）/2」（?）m/2」（?）（m-1）/2」for m=5, 6, 7 and for m≥5 with even n≥4, and the equality holds for m=5, 6, 7 and for m=8, 9, 10 with even n≥4.The thesis also studies the Cartesian product of path with complete graph K_m, complete bipartite graph K_m,l and cone, respectively. A special crossing counting method for the Cartesian product with paths is presented to obtain lower bounds of cr（K_m□P_n）, cr(K_2,l□P_n), cr（W_m□P_n） and cr(W_2.m□P_n). And the crossing number of K₆□P_n, K_2,1□P_n, W_m□P_n and W_2,m□P_n are determined.Finally, we use the counting methods developed in this thesis to study other crossing number problems. As application examples, the crossing numbers of Kn（?）del graph J_3,n and Flower Snark and related graph F_n are determined.更多还原