胡宁贝，魏首柳，白银燕

(闽江学院 数学系，福建 福州 350121)

树Tn与路Pm的笛卡尔积图的交叉数

胡宁贝，魏首柳，白银燕

(闽江学院 数学系，福建 福州 350121)

图的交叉数是图论中一个重要的研究课题.分别记含有n+1个顶点的树和路为Tn与Pn，通过数学归纳法验证并计算得到了笛卡尔积图Tn×Pm的交叉数，其中n≤4.

笛卡尔积图；好画法；交叉数；树；路

令G表示一个简单连通图.设V(G)和E(G)分别表示图G的顶点集和边集.G1×G2表示图G1和G2的笛卡尔积图，具体定义如下：V(G1×G2)=V(G1)×V(G2)，E(G1×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2E(G2)或者u2=v2且u1v1E(G1)}.图的交叉数问题是近代图论中一个重要的研究课题.图G的交叉数[1]指图G在平面上所有好画法中边与边之间相互交叉的最小顶点数，用cr(G)表示.其中，好画法满足：①相互交叉的任何两条边最多仅在顶点处交叉；②边不能自身相交；③有相同端点的两条边不交叉；④任何3条边都不可能交叉于同一顶点.最优画法指含最小交叉数的好画法，用crD(G)表示图G在好画法时D的交叉数.如果没有特别说明，本研究涉及的一些概念和术语均来自文献[2].

图的交叉数的确定问题不仅在理论研究中具有非常重要的意义，而且在诸多实际问题中也有相应的研究背景，如超大规模集成电路VLSL中圈的布局[3-5]、离散几何与计算几何的研究及软件开发过程中文档的实体联系图(ER图)的自动生成和工业上电子线路板设计中的布线问题等.

国内外学者对图的交叉数的计算问题已经做了大量的分析和研究,也得到了一些成果.1993年,Garey和Johnson[6]研究并证明了图的交叉数……