双广义Petersen图DP(7,1)的交叉数

The Crossing Number of Double Generalized Petersen Graph DP(7,1)

摘要: 图的交叉数是图论的一个重要的分支，近百年以来，国内外诸多学者对于图的交叉数这一问题进行了广泛且深入的研究。事实上已证实确定一个图的交叉数问题是NP-完全问题。由于证明难度较大，国内外关于图的交叉数目问题的研究进展缓慢。本文主要采用反证法研究了双广义Petersen图DP(7,1)的交叉数，给出双广义Petersen图DP(7,1)的交叉数为7的一个好的画法。采用反证法，将图DP(7,1)的边集分为互不相交的7组，对所有可能情形进行讨论，从而确定交叉数的下界至少是7，得到图DP(7,1)的交叉数的精确值。

Abstract: The crossing number of graphs plays an important role in graph theory. In the last hundred years, many scholars have conducted extensive and in-depth research on the problem of graph crossing numbers at home and abroad. In fact, a number of scholars have proved that determining the crossing number of a graph is a NP-complete problem. Due to the difficulty of proof, scholars at home and abroad have experienced a difficult process in the field of the crossing numbers. This pa-per mainly studies the crossing number of double generalized Petersen graph DP(7,1) and use proof by contradiction; a drawing of a crossing number of 7 for the double generalized Petersen graph DP(7,1) is given by the definition of a good drawing. Firstly, the edge sets of graph DP(7,1) are divided into 7 groups that do not intersect each other; secondly, all possible cases are discussed to determine that the lower bound of the crossing number of graph DP(7,1) is at least 7; finally, the exact value of the crossing number of graph DP(7,1) is obtained.

1. 交叉数的研究进展

近代图论中发展了图的交叉数这一概念，交叉数是图论中的重要分支，起源于上个世纪五十年代Turan [1] 遇到的砖厂运砖这一实际问题，一经提出，不断吸引国内外众多学者研究，研究图的交叉数问题不仅在拓扑图论研究中具有不可替代的作用，同时在其它学科领域也有重要的应用，如生物工程DNA的图示，电子线路板设计的布线等。由于图的自身结构复杂，对于具体图类的研究绝非易事，Garey，Johnson [2] 已经证实证明图的交叉数问题是一个NP-完全问题，至今，国内外也进行了许多研究，主要研究成果如下。

1.1. 完全图

上个世纪七十年代，R.K. Guy [3] 首次在文献中提出关于完全图 $K_n$ 的猜想：对于任意的 $n\ge 1$ ，有

$Z\left(n\right)=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor .$

对任意实数x， $\lfloor x\rfloor$ 表示不超过x的最大整数。

1969年R.K. Guy [4] 对 $n\ge 10$ 进行了验证，目前的最优结果对于 $n=11,12$ 上面公式成立。

Blazek，Koman等人 [5] 在60年代中期的研究表明上述公式给出的是完全图 $K_n$ 的交叉数的一个上界。即：

$cr\left(K_n\right)\le \frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor .$

1970年根据Kleitman [6] 的关于完全二分图的交叉数的结果，对足够大的n有如下的公式成立：

$cr\left(K_n\right)\ge n\left(n-1\right)\left(n-2\right)\left(n-3\right)/80.$

Richter等人得到了 $K_{n-1}$ 与 $K_n$ 的关系 [7] [8] ：

$cr\left(K_n\right)\ge \lceil \frac{n}{n-4}\cdot cr\left(K_{n-1}\right)\rceil .$

2002年Alcholzer，Aurenhammer和Krasser [9] 利用计算机穷举方法证明了 $K_{11}$ 和 $K_{12}$ 的交叉数分别为100和150，并给出了 $K_{13}$ 的交叉数为229。

1.2. 广义Petersen图

不少学者就广义Petersen图进行了广泛的研究，最早于1981年，Exoo，Harary和Kabel [10] 证明了：

$\{\begin{array}{l}cr\left(P\left(n,2\right)\right)=0,若n为偶数或n=3;\\ cr\left(P\left(n,2\right)\right)=2,若n=5;\\ cr\left(P\left(n,2\right)\right)=3,若n为奇数或n\ge 7.\end{array}$

1986年Fiorini [11] 对广义Petersen图的交叉数进行研究，计算出当 $n\ge 14$ 时所有图 $P\left(n,k\right)$ 的交叉数的具体值，然而Fiorini的证明存在错误。对于 $cr\left(P\left(9,3\right)\right)=2$ 给出了的数学证明，确定了 $cr\left(P\left(10,3\right)\right)=4$ ，并且

$\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,\left(h\ge 4\right);\\ h+3\le cr\left(P\left(3h+1,3\right)\right)\le h+1,\left(h\ge 3\right);\\ cr\left(P\left(3h+2,3\right)\right)=h+2,\left(h\ge 2\right).\end{array}$

2002年，Richter [12] 和Sarazin指出Fiorini在证明 $C\left(n:\left\{\text{1},\text{3}\right\}\right)$ 的交叉数的下界时有漏洞，并以 $cr\left(P\left(10,3\right)\right)=6$ ， $cr\left(P\left(11,3\right)\right)=5$ ， $cr\left(P\left(12,3\right)\right)=4$ 为起点，用数学归纳法重新证明并对其结论进行了更正：

$\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,\left(h\ge 4\right);\\ cr\left(P\left(3h+1,3\right)\right)=h+3,\left(h\ge 3\right);\\ cr\left(P\left(3h+2,3\right)\right)=h+2,\left(h\ge 3\right).\end{array}$

2004年，林晓惠 [13] 在其论文中得出了 $P\left(\text{4}k+\text{2},\text{2}k\right)$ 等部分广义Petersen图的交叉数的上界。

2005年，马登举 [14] 等人得到了广义Petersen图 $G\left(\text{2}m+\text{1},m\right)$ 的交叉数。

2009年，杨元生 [15] 等人利用算法给出了 $n\le 16$ 时 $P\left(n,k\right)$ 的交叉数的精确值。

Fiorini和黄元秋 [16] 等人分别用不同方法证明了 $P\left(3k,k\right)$ 的交叉数。

2012年，周进鑫、冯衍全 [17] 在广义Petersen图的基础上，首次提出双广义Petersen图的概念，并随后证明了双广义Petersen图不是点传递图。

2013年，郑百功 [18] 在硕士论文中总结了其子图画法的一些性质并给出一种新的对偶图的定义，进而按照这种对偶图的不同情况证明了 $P\left(10,3\right)$ 的交叉数的精确值为6。

2. 双广义Petersen图DP(7,1)的交叉数

2.1. 双广义Petersen图DP(7,1)

令双广义Petersen图DP(7,1)的顶点集与边集分别为： $V\left(DP\left(7,1\right)\right)=\left\{x_i,y_i,u_i,v_i:0\le i\le 6\right\}$ ； $E\left(DP\left(7,1\right)\right)=\left\{x_i{x}_{i+1},y_i{y}_{i+1}:0\le i\le 6\right\}\cup \left\{u_i{v}_{i+1},v_i{u}_{i+1}:0\le i\le 6\right\}$ 。由于双广义Petersen图DP(7,1)是一个简单图，记为G。图G的一个分解是子图的列表，使得图G中的每一条都恰好在其中的一个子图中。

将图G的边集分为7个互不相交的子集，令 $H_i$ 的顶点集与边集分别表示为

$V\left(H_i\right)=\left\{x_i,x_{i+1},y_i,y_{i+1},u_i,u_{i+1},v_i,v_{i+1}\right\}$ ， $E\left(H_i\right)=\left\{x_i{x}_{i+1},x_i{u}_i,u_i{v}_{i+1},y_i{y}_{i+1},y_i{v}_i,v_i{u}_{i+1}\right\}$ ， $0\le i\le 6$ ，可得到 $\left\{H_0,H_1,\cdots ,H_6\right\}$ 为图G的一个可传递分解。

用 $f_D\left(H_i\right)$ 表示在画法D下与 $H_i$ 相关的交叉点数目的函数，如下：

$f_D\left(H_i\right)=c{r}_D\left(H_i\right)+c{r}_D\left(H_i,DP\left(7,1\right)\backslash E\left(H_i\right)\right)/2$

令D为双广义Petersen图DP(7,1)的一个好的画法，在画法D下的交叉数以 $cr\left(D\right)$ 或者 $c{r}_D\left(G\right)$ 表示。对于DP(7,1)的给定画法D，

$cr\left(D\right)={\displaystyle {\sum }_{i=0}^6{f}_D}\left(H_i\right).$

令 $C\left(x_i,x_{i+1},x_{i+2},u_{i+2},v_{i+1},u_i\right)$ 与 $C\left(y_i,y_{i+1},y_{i+2},v_{i+2},u_{i+1},v_i\right)$ 分别表示圈 $x_i{x}_{i+1}{x}_{i+2}{u}_{i+2}{v}_{i+1}{u}_i{x}_i$ 与圈 $y_i{y}_{i+1}{y}_{i+2}{v}_{i+2}{u}_{i+1}{v}_i{y}_i$ ， $0\le i\le 6$ 。令 $W_i=\left\{x_i,u_i,y_i,v_i\right\}$ ， $B_i$ 是 $W_i$ 诱导DP(7,1)的子图， $B_{i,i+1}=B_i\cup B_{i+1}$ 且 $C_i=H_i\cup B_{i+1}$ ， $0\le i\le 6$ 。

若 $0\le i\le t$ ，令c为一个正实数，若存在一个正整数 $l_i$ 满足 $f_D\left(H_{i,i-1+l_i}\right)\ge l_{i}c$ ，则令 $l_c^D\left(H_i\right)$ 为使得 $f_D\left(H_{i,i-1+l_i}\right)\ge l_{i}c$ 成立的 $l_i$ 的最小值，反之若这样的 $l_i$ 不存在，则 $l_c^D\left(H_i\right)=+\infty$ 。

Jordan曲线定理任意一条简单(不自交)闭曲线J把平面分成两个区域，在不同区域的两点若要相连，则连结的弧必定与J相交。

根据Jordan曲线定理，则有以下引理：

引理2.1 在图G中，若C与 $C^{\prime }$ 为两个顶点不相交的圈， $P_t=u_1{u}_2\cdots u_t$ 为t阶路径且 $V\left(P_t\right)\cap V\left(C\right)=\varnothing$ ，假设D是图G的一个好的画法，若 $u_i$ 与 $u_t$ 位于 $D\left(C\right)$ 所在区域边界划分平面的相同区域，则 $c{r}_D\left(C,C^{\prime }\right)$ 为偶数；反之若 $u_i$ 与 $u_t$ 位于 $D\left(C\right)$ 所在区域边界划分平面的不同区域，那么 $c{r}_D\left(C,C^{\prime }\right)$ 为奇数，后述记为引理2。

2.2. 双广义Petersen图DP(7,1)的交叉数上界

引理2.2 对于双广义Petersen图DP(7,1)的一个好的画法D，存在 $cr\left(D\right)<7$ 。

证明：如图1所示，给出了双广义Petersen图DP(7,1)的一个好的画法

Figure 1. A good drawing of DP(7,1)

图1. DP(7,1)的一个好的画法

2.3. 双广义Petersen图DP(7,1)的交叉数下界

假设D为双广义Petersen图DP(7,1)的一个好的画法，由引理2.2可知 $cr\left(D\right)<7$ 。若 $0\le i\le 6$ ，这里将 $l_{61/70}^D\left(H_i\right)$ 简记为 $l_i^D$ ，显然 $DP\left(7,1\right)\backslash E\left(B_{i,i+1}\right)$ 为 $DP\left(5,1\right)$ 的一个子图。

引理2.3 $c{r}_D\left(B_{i,i+1}\right)+c{r}_D\left(B_{i,i+1},DP\left(7,1\right)\backslash E\left(B_{i,i+1}\right)\right)\le 2$ ， $0\le i\le 6$ 。

引理2.4 若 $l_i^D\ge 4$ ， $0\le i\le 6$ ，则 $c{r}_D\left(C_i\right)=0$ 。

证明：反证法，不失一般性，假设 $c{r}_D\left(C_0\right)\ge 1$ ，由于 $l_i^D\ge 4$ ，则 $f_D\left(H_0\right)<61/70$ ， $f_D\left(H_{0,1}\right)<122/70$ ， $f_D\left(H_{0,2}\right)<183/70$ 。由 $f_D\left(H_{0,1}\right)<122/70$ 且 $c{r}_D\left(C_0\right)\ge 1$ ，则 $c{r}_D\left(H_{0,1}\right)=1$ 且 $c{r}_D\left(C_0\right)=1$ 。根据 $f_D\left(H_{0,2}\right)<183/70$ ，则 $c{r}_D\left(H_{0,1}\cup B_2\right)\le 2$ 。在画法D中，若 $C\left(x_0,x_1,x_2,u_2,v_1,u_0\right)$ 相交叉于

$C\left(y_0,y_1,y_2,v_2,u_1,v_0\right)$ ，则由引理2可知 $c{r}_D\left(C\left(x_0,x_1,x_2,u_2,v_1,u_0\right),C\left(y_0,y_1,y_2,v_2,u_1,v_0\right)\right)=0$ ，与

$f_D\left(H_{0,2}\right)<183/70$ 相矛盾，因此 $c{r}_D\left(C\left(x_0,x_1,x_2,u_2,v_1,u_0\right),C\left(y_0,y_1,y_2,v_2,u_1,v_0\right)\right)=0$ 。

假设 $c{r}_D\left(H_{0,1}\cup B_2\right)=2$ ，根据 $c{r}_D\left(H_{0,1}\right)=1$ ，则 $B_2$ 一定被交叉。不失一般性，假设在 $D\left(H_{0,1}\cup B_2\right)$ 中 $x_2{u}_2$ 被交叉，由于 $c{r}_D\left(C\left(x_0,x_1,x_2,u_2,v_1,u_0\right),C\left(y_0,y_1,y_2,v_2,u_1,v_0\right)\right)=0$ 且D是一个好的画法，则 $c{r}_D\left(x_2{u}_2,C_0\right)=1$ 。由引理2可知 $x_2$ 与 $u_2$ 在 $D\left(C_0\right)$ 所在区域边界划分平面的不同区域，因此路径 $x_2{x}_3{x}_4{u}_4{v}_3{u}_2$ 相交于 $C_0$ 至少一次，则在D中 $C_0$ 至少被交叉三次。又由引理2.3可知

$c{r}_D\left(B_1\right)+c{r}_D\left(B_1,DP\left(7,1\right)\backslash E\left(B_1\right)\right)\le 2$ ，因此由于 $f_D\left(H_0\right)<61/70$ ，那么路径 $x_2{u}_2$ 或 $x_2{x}_3{x}_4{u}_4{v}_3{u}_2$ 相交于 $H_0$ 一次，则 $c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=1$ 。

由于 $c{r}_D\left(H_{0,1}\cup B_2\right)=2$ ， $c{r}_D\left(x_2{u}_2,C_0\right)=1$ 且 $c{r}_D\left(C_0\right)=1$ ，则 $c{r}_D\left(C_0,u_1{v}_2{y}_2{y}_1\right)=0$ 。由于

$c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=1$ 且 $c{r}_D\left(C_0,u_1{v}_2{y}_2{y}_1\right)=0$ ，则 $D\left(C_0\cup u_1{v}_2{y}_2{y}_1\right)$ 分别同构于图2(a)，图2(b)。若 $D\left(C_0\cup u_1{v}_2{y}_2{y}_1\right)$ 同构于图2(a)，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $x_1{u}_1{v}_2{y}_2{y}_1{v}_1$ 至少各产生一个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾。若 $D\left(C_0\cup u_1{v}_2{y}_2{y}_1\right)$ 同构于图2(b)，由引理2可知路径 $x_0{x}_6{x}_5{x}_4{x}_3{u}_3{v}_2$ ， $u_0{v}_6{y}_6{y}_5{y}_4{y}_3{y}_2$ 相交于 $x_1{u}_1{v}_0{y}_0{y}_1{v}_1$ 至少各产生一个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，因此由于 $c{r}_D\left(H_{0,1}\cup B_2\right)\le 2$ 且 $c{r}_D\left(C_0\right)=1$ ，则 $c{r}_D\left(H_{0,1}\cup B_2\right)=1$ 。

(a) (b) (c) (d) (e)

Figure 2. Good drawings of $D\left(C_0\cup u_1{v}_2{y}_2{y}_1\right)$

图2. $D\left(C_0\cup u_1{v}_2{y}_2{y}_1\right)$ 的好的画法

由于 $f_D\left(H_0\right)<61/70$ 且 $c{r}_D\left(C_0\right)=1$ ，不失一般性，假设在 $D\left(C_0\right)$ 中 $v_1{y}_1$ 被交叉，若 $c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=1$ ，则 $D\left(H_{0,1}\cup B_2\right)$ 分别同构于图2(c)~(e)。若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图2(c)，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 同时相交于 $x_1{u}_1{v}_2{y}_2{y}_1{v}_1$ ， $u_1{x}_1{x}_2{u}_2{v}_1{y}_1$ 至少各产生两个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾。若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图2(d)，由引理2可知路径 $u_2{v}_3{u}_4{v}_5{u}_6{v}_0$ ， $x_2{x}_3{x}_4{x}_5{u}_5{v}_6{y}_6{y}_0$ 同时相交于 $x_1{u}_1{v}_2{y}_2{y}_1{v}_1$ ， $u_1{x}_1{x}_0{u}_0{v}_1{y}_1$ 至少各产生两个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾。若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图2(e)，由引理2可知路径 $u_2{v}_3{y}_3{y}_2$ ， $x_2{x}_3{u}_3{v}_2$ 同时相交于 $x_1{u}_1{v}_0{y}_0{y}_1{v}_1$ ， $u_1{x}_1{x}_0{u}_0{v}_1{y}_1$ 至少各产生两个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，因此 $c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=0$ 。由于 $c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=0$ ，若 $x_2$ 与 $v_2$ 在 $D\left(C_0\right)$ 划分平面的不同区域，由引理2可知路径 $u_2{v}_3{y}_3{y}_2$ ， $x_2{x}_3{u}_3{v}_2$ 相交于 $C_0$ 至少各产生一个交叉。又由引理2.3可知 $c{r}_D\left(B_1\right)+c{r}_D\left(B_1,DP\left(7,1\right)\backslash E\left(B_1\right)\right)\le 2$ 且 $c{r}_D\left(v_1{y}_1,x_1{u}_1\right)=0$ ，则 $f_D\left(H_0\right)\ge 1$ ，产生矛盾，因此 $x_2$ 与 $v_2$ 在 $D\left(C_0\right)$ 划分平面的相同区域。若 $x_2$ 与 $u_2$ 在 $D\left(C_0\right)$ 划分平面的不同区域，由引理2可知路径 $x_2{u}_2$ ， $x_2{x}_3{x}_4{u}_4{v}_3{u}_2$ 相交于 $C_0$ 至少各产生一个交叉，与 $f_D\left(H_{0,1}\right)<122/70$ 相矛盾，因此 $x_2$ 与 $u_2$ 在 $D\left(C_0\right)$ 划分平面的相同区域。则 $D\left(H_{0,1}\cup B_2\right)$ 分别同构于图3(a)~(d)。

(a) (b) (c) (d)

Figure 3. Good drawings of $D\left(H_{0,1}\cup B_2\right)$ with $c{r}_D\left(C_0\right)=1$

图3. $D\left(H_{0,1}\cup B_2\right)$ 在 $c{r}_D\left(C_0\right)=1$ 下的好的画法

若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图3(a)，由引理2可知路径 $x_0{x}_6{x}_5{u}_5{v}_6{u}_0$ ， $v_0{u}_6{v}_5{u}_4{x}_4{x}_3{x}_2$ ， $y_0{y}_6{y}_5{y}_4{y}_3{v}_3{u}_2$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉。由引理2.3可知 $c{r}_D\left(B_{1,2}\right)+c{r}_D\left(B_{1,2},DP\left(7,1\right)\backslash E\left(B_{1,2}\right)\right)\le 2$ ，则路径 $x_0{x}_6{x}_5{u}_5{v}_6{u}_0$ ， $v_0{u}_6{v}_5{u}_4{x}_4{x}_3{x}_2$ 或 $y_0{y}_6{y}_5{y}_4{y}_3{v}_3{u}_2$ 最多交叉于 $B_1$ 或者 $B_2$ 一次，与 $f_D\left(H_{0,1}\right)<122/70$ 相矛盾。

若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图3(b)，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉，由于 $f_D\left(H_{0,2}\right)<183/70$ ，则 $c{r}_D\left(x_2{x}_3\cup v_2{u}_3,H_{0,1}\cup B_2\right)=0$ 。由引理2可知，若 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的不同区域，则路径 $x_3{u}_3$ ， $x_3{x}_4{x}_5{u}_5{v}_4{u}_3$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，因此 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的相同区域，由引理2可知若 $x_3{u}_3$ 相交于 $H_{0,1}\cup B_2$ 至少产生两个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，则 $c{r}_D\left(x_2{x}_3{u}_3{v}_2,H_{0,1}\cup B_2\right)=0$ 。同理可证， $c{r}_D\left(u_2{v}_3{y}_3{y}_2,H_{0,1}\cup B_2\cup x_2{x}_3{u}_3{v}_2\right)=0$ ，则 $D\left(H_{0,2}\cup B_3\right)$ 同构于图4(a)。如图4(a)所示，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $v_3{y}_3{y}_2{y}_1{v}_1{u}_2{v}_3$ ，由引理2可知若路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_2{v}_3{y}_3{y}_2$ ，则路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_2{v}_3{y}_3{y}_2{v}_2{u}_3{x}_3{x}_2{u}_2$ 至少两次，若路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $u_2{v}_3{y}_3{y}_2$ ，情形一致。又由于 $f_D\left(H_{0,1}\right)<122/70$ 可知 $v_1{y}_1{y}_2$ 被路径 $u_0{v}_6{y}_6{y}_0$ 或 $x_0{x}_6{u}_6{v}_0$ 交叉最多一次，因此路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $H_{0,2}\cup B_3$ 至少产生三个交叉。若路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $v_1{y}_1{y}_2$ 可知 $x_6$ ， $u_6$ 在区域 $R_2$ ， $R_4$ 或 $R_6$ 中，由引理2可知路径 $x_6{x}_5{x}_4{x}_3$ ， $u_6{v}_5{y}_5{y}_4{v}_4{u}_3$ 相交于 $H_{0,2}\cup B_3$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $y_1{v}_1{u}_2$ 。若路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $y_1{v}_1{u}_2$ ，根据引理2可知 $v_6$ ， $y_6$ 在区域 $R_2$ ， $R_4$ 或 $R_6$ 中，由引理2可知路径 $v_6{u}_5{v}_4{u}_3$ ， $y_6{y}_5{v}_5{u}_4{x}_4{x}_3$ 相交于 $H_{0,2}\cup B_3$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾。

若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图3(c)，由引理2可知路径 $v_0{u}_6{v}_5{y}_5{y}_6{y}_0$ ， $u_0{v}_6{u}_5{v}_4{y}_4{y}_3{y}_2$ ， $x_0{x}_6{x}_5{x}_4{x}_3{u}_3{v}_2$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉。由引理2.3可知 $c{r}_D\left(B_{1,2}\right)+c{r}_D\left(B_{1,2},DP\left(7,1\right)\backslash E\left(B_{1,2}\right)\right)\le 2$ ，则路径 $v_0{u}_6{v}_5{y}_5{y}_6{y}_0$ ， $u_0{v}_6{u}_5{v}_4{y}_4{y}_3{y}_2$ 或 $x_0{x}_6{x}_5{x}_4{x}_3{u}_3{v}_2$ 最多交叉于 $B_1$ 或者 $B_2$ 一次，与 $f_D\left(H_{0,1}\right)<122/70$ 相矛盾。

若 $D\left(H_{0,1}\cup B_2\right)$ 同构于图3(d)，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉，由于 $f_D\left(H_{0,2}\right)<183/70$ ，则 $c{r}_D\left(x_2{x}_3\cup v_2{u}_3,H_{0,1}\cup B_2\right)=0$ 。由引理2可知，若 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的不同区域，则路径 $x_3{u}_3$ ， $x_3{x}_4{x}_5{u}_5{v}_4{u}_3$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，因此 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的相同区域，由引理2可知若 $x_3{u}_3$ 相交于 $H_{0,1}\cup B_2$ 至少产生两个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，则 $c{r}_D\left(x_2{x}_3{u}_3{v}_2,H_{0,1}\cup B_2\right)=0$ 。同理可证， $c{r}_D\left(u_2{v}_3{y}_3{y}_2,H_{0,1}\cup B_2\cup x_2{x}_3{u}_3{v}_2\right)=0$ ，则 $D\left(H_{0,2}\cup B_3\right)$ 同构于图4(b)。如图4(b)所示，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $v_3{y}_3{y}_2{y}_1{v}_1{u}_2{v}_3$ ，由引理2可知若路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_2{v}_3{y}_3{y}_2$ ，则路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_2{v}_3{y}_3{y}_2{v}_2{u}_3{x}_3{x}_2{u}_2$ 至少两次，若路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $u_2{v}_3{y}_3{y}_2$ ，情形一致。又由于 $f_D\left(H_{0,1}\right)<122/70$ 可知 $y_1{v}_1{u}_2$ 被路径 $u_0{v}_6{y}_6{y}_0$ 或 $x_0{x}_6{u}_6{v}_0$ 交叉最多一次，因此路径 $x_0{x}_6{u}_6{v}_0$ ， $u_0{v}_6{y}_6{y}_0$ 相交于 $H_{0,2}\cup B_3$ 至少产生三个交叉。若路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $y_1{v}_1{u}_2$ 可知 $x_6$ ， $u_6$ 在区域 $R_2$ ， $R_4$ 或 $R_6$ 中，由引理2可知路径 $x_6{x}_5{x}_4{x}_3$ ， $u_6{v}_5{y}_5{y}_4{v}_4{u}_3$ 相交于 $H_{0,2}\cup B_3$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $y_1{v}_1{u}_2$ 。若路径 $u_0{v}_6{y}_6{y}_0$ 相交于 $y_1{v}_1{u}_2$ ，根据引理2可知 $v_6$ ， $y_6$ 在区域 $R_2$ ， $R_4$ 或 $R_6$ 中，由引理2可知路径 $v_6{u}_5{v}_4{u}_3$ ， $y_6{y}_5{v}_5{u}_4{x}_4{x}_3$ 相交于 $H_{0,2}\cup B_3$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则 $c{r}_D\left(C_0\right)=0$ 。

(a) (b)

Figure 4. Good drawing of $D\left(H_{0,2}\cup B_3\right)$

图4. $D\left(H_{0,2}\cup B_3\right)$ 的好的画法

引理2.5 若 $l_0^D\ge 4$ ， $c{r}_D\left(C_0\right)=0$ ， $c{r}_D\left(H_{0,1}\cup B_2\right)=1$ 且 $c{r}_D\left(C_0,x_1{x}_2\cup y_1{y}_2\right)=1$ ，则 $D\left(H_{0,1}\cup B_2\right)$ 同构于图5中的一个图。

证明：由于 $l_0^D\ge 4$ ，得到 $f_D\left(H_0\right)<61/70$ ， $f_D\left(H_{0,1}\right)<122/70$ ， $f_D\left(H_{0,2}\right)<183/70$ 。因为

$c{r}_D\left(H_{0,1}\cup B_2\right)=1$ 和 $H_{0,1}\cup B_2=C_0\cup \left(x_1{x}_2{u}_2{v}_1\cup y_1{y}_2{v}_2{u}_1\right)$ ，则

$c{r}_D\left(C_0,x_1{x}_2{u}_2{v}_1\cup y_1{y}_2{v}_2{u}_1\right)+c{r}_D\left(x_1{x}_2{u}_2{v}_1\cup y_1{y}_2{v}_2{u}_1\right)=1$ 。由 $c{r}_D\left(C_0,x_1{x}_2\cup y_1{y}_2\right)=1$ ，不失一般性令 $c{r}_D\left(C_0,x_1{x}_2\right)=1$ 。由于 $c{r}_D\left(H_{0,1}\cup B_2\right)=1$ 且 $c{r}_D\left(C_0,x_1{x}_2\right)=1$ ，那么 $x_2$ 和 $u_2$ 位于 $C_0$ 划分平面的同一区域， $v_2$ 和 $y_2$ 位于 $C_0$ 划分平面的同一区域。根据引理2可知，若 $x_2$ 与 $v_2$ 位于 $C_0$ 划分平面的不同区域，则路径 $x_2{x}_3{u}_3{v}_2$ 交 $C_0$ 至少产生一个交叉，路径 $u_2{v}_3{y}_3{y}_2$ 交 $C_0$ 至少产生一个交叉，与 $f_D\left(H_{0,1}\right)<122/70$ 相矛盾，所以 $v_2$ 与 $x_2$ 位于 $C_0$ 划分平面的同一区域。根据引理2可知

$c{r}_D\left(C\left(x_0,x_1,x_2,u_2,v_1,u_0\right),C\left(y_0,y_1,y_2,v_2,u_1,v_0\right)\right)=0$ 。又由好的画法的定义可知 $x_1{x}_2$ 只能相交于 $x_0{u}_0$ ， $u_0{v}_1$ 或 $v_1{y}_1$ ，则 $D\left(H_{0,1}\cup B_2\right)$ 同构于图5中的一个图。

(a) (b) (c)

Figure 5. A good drawing of $H_{0,1}\cup B_2$ if $x_1{x}_2$ crosses $x_0{u}_0{v}_1{y}_1$

图5. $H_{0,1}\cup B_2$ 在 $x_1{x}_2$ 交 $x_0{u}_0{v}_1{y}_1$ 下的一个好的画法

引理2.6 令D是一个好的画法，若 $l_0^D\ge 5$ 且 $D\left(H_{0,1}\cup B_2\right)$ 同构于图5(a)，则 $cr\left(D\right)\ge 7$ 。

证明：反证法，假设 $cr\left(D\right)\le 6$ 。由于 $l_0^D\ge 5$ ，得到 $f_D\left(H_0\right)<61/70$ ， $f_D\left(H_{0,1}\right)<122/70$ ， $f_D\left(H_{0,2}\right)<183/70$ ， $f_D\left(H_{0,3}\right)<244/70$ ， $f_D\left(H_{0,4}\right)<305/70$ 。

如图5(a)所示，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $y_0{y}_6{v}_6{u}_0$ 交叉于 $H_{0,1}\cup B_2$ ，则 $H_{0,1}\cup B_2$ 的边被交叉至少两次。又由于 $f_D\left(H_{0,2}\right)<183/70$ ，则 $c{r}_D\left(v_2{u}_3\cup x_2{x}_3,H_{0,1}\cup B_2\right)=0$ 。若 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的不同区域，由引理2可知路径 $x_3{u}_3$ ， $x_3{x}_4{x}_5{u}_5{v}_4{u}_3$ 相交于 $H_{0,1}\cup B_2$ 至少各产生一个交叉，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，则 $x_3$ 与 $u_3$ 位于 $D\left(H_{0,1}\cup B_2\right)$ 划分平面的同一区域。若 $x_3{u}_3$ 相交于 $H_{0,1}\cup B_2$ ，由引理2可知 $H_{0,1}\cup B_2$ 的边被交叉至少两次，与 $f_D\left(H_{0,2}\right)<183/70$ 相矛盾，则 $c{r}_D\left(x_3{u}_3,H_{0,1}\cup B_2\right)=0$ 。 $D\left(H_{0,1}\cup B_2\cup v_2{u}_3{x}_3{x}_2\right)$ 同构于图6(a)。如图6(a)所示，根据引理2可知路径 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_0{v}_1{y}_1{y}_2{v}_2{u}_1{x}_1{x}_2$ ，若 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_0{v}_1{y}_1{y}_2{v}_2$ ，由引理2可知 $x_0{x}_6{u}_6{v}_0$ 相交于 $u_0{v}_1{y}_1{y}_2{v}_2{u}_1{x}_1{x}_2$ 至少产生两个交叉。同理 $y_0{y}_6{v}_6{u}_0$ 相交于 $u_0{v}_1{y}_1{y}_2{v}_2{u}_1{x}_1{x}_2$ 的情形完全一致。又由 $f_D\left(H_{0,2}\right)<183/70$ 可知 $v_2{u}_1{x}_1{x}_2$ 被路径 $x_0{x}_6{u}_6{v}_0$ 或 $y_0{y}_6{v}_6{u}_0$ 交叉至多一次，从而路径 $x_0{x}_6{u}_6{v}_0$ ， $y_0{y}_6{v}_6{u}_0$ 相交于 $H_{0,1}\cup B_2\cup v_2{u}_3{x}_3{x}_2$ 至少三次。由 $f_D\left(H_{0,3}\right)<244/70$ ，可以得到 $c{r}_D\left(u_2{v}_3{y}_3{y}_2,H_{0,1}\cup B_2\cup v_2{u}_3{x}_3{x}_2\right)=0$ 和 $c{r}_D\left(y_2{y}_3,u_2{v}_3\right)=0$ ，则 $D\left(H_{0,2}\cup B_3\right)$ 同构于图6(b)。

(a) (b) (c) (d)

Figure 6. Sub-drawings from D with $x_1{x}_2$ crosses $u_0{v}_1$

图6. 在 $x_1{x}_2$ 交 $u_0{v}_1$ 下D的子画法

如图6(b)所示，若 $x_4$ 与 $u_4$ 位于 $D\left(H_{0,2}\cup B_3\right)$ 划分平面的不同区域，由引理2可知路径 $x_4{u}_4$ ， $x_4{x}_5{u}_5{v}_4{y}_4{y}_5{v}_5{u}_4$ 交于 $H_{0,2}\cup B_3$ 至少各产生一个交叉，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则 $x_4$ 与 $u_4$ 位于 $D\left(H_{0,2}\cup B_3\right)$ 划分平面的同一区域。如果 $x_4{u}_4$ 交叉于 $H_{0,2}\cup B_3$ ，由引理2可知 $H_{0,2}\cup B_3$ 的边被交叉至少两次，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，因此 $c{r}_D\left(x_4{u}_4,H_{0,2}\cup B_3\right)=0$ 。又由于 $f_D\left(H_{0,3}\right)<244/70$ ，则 $c{r}_D\left(x_3{x}_4\cup v_3{u}_4,H_{0,2}\cup B_3\right)=0$ ， $c{r}_D\left(x_3{x}_4,v_3{u}_4\right)=0$ 。 $D\left(H_{0,2}\cup B_3\cup x_3{x}_4{u}_4{v}_3\right)$ 同构于图6(c)。

如图6(c)所示，由引理2可知路径 $x_0{x}_6{u}_6{v}_0$ ， $y_0{y}_6{v}_6{u}_0$ 相交于 $H_{0,1}\cup B_2\cup v_2{u}_3{x}_3{x}_2$ 至少产生三个交叉，又由 $f_D\left(H_{0,3}\right)<244/70$ 可知 $c{r}_D\left(u_3{v}_4\cup y_3{y}_4,H_{0,2}\cup B_3\right)=0$ 和 $c{r}_D\left(u_3{v}_4,y_3{y}_4\right)=0$ 。若 $v_4{y}_4$ 相交于 $C\left(x_2,x_3,x_4,u_4,v_3,u_2\right)$ ，由引理2.2可知 $v_4{y}_4$ 所在的圈 $C\left(y_2,y_3,y_4,v_4,u_3,v_2\right)$ 交于圈 $C\left(x_2,x_3,x_4,u_4,v_3,u_2\right)$ 至少产生两个交叉，与 $f_D\left(H_{0,4}\right)<305/70$ 相矛盾，因此 $c{r}_D\left(v_4{y}_4,C\left(x_2,x_3,x_4,u_4,v_3,u_2\right)\right)=0$ 。若 $v_4$ 和 $y_4$ 位于 $D\left(H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)\right)$ 划分平面的不同区域，由引理2可知路径 $v_4{y}_4$ ， $v_4{u}_5{x}_5{x}_4{u}_4{v}_5{y}_5{y}_4$ 交叉于 $H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)$ ，则 $H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)$ 的边被交叉至少两次，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则 $v_4$ 与 $y_4$ 位于 $D\left(H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)\right)$ 划分平面的同一区域。如果 $v_4{y}_4$ 相交于 $H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)$ ，由引理2可知 $H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)$ 的边被交叉至少两次，与 $f_D\left(H_{0,3}\right)<244/70$ 相矛盾，则 $c{r}_D\left(v_4{y}_4,H_{0,2}\cup B_3\backslash E\left(x_3{x}_2{u}_2{v}_3\right)\right)=0$ 。 $D\left(H_{0,3}\cup B_4\right)$ 同构于图6(d)。如图6(d)所示，由引理2可知路径 $u_0{v}_6{u}_5{v}_4$ 相交于 $H_{0,3}\cup B_4$ 至少产生一个交叉，路径 $v_0{u}_6{x}_6{x}_5{x}_4$ ， $y_0{y}_6{y}_5{v}_5{u}_4$ 相交于 $H_{0,3}\cup B_4$ 至少各产生两个交叉，因此对于D有 $cr\left(D\right)\ge 6$ 。由假设 $cr\left(D\right)\ge 6$ ，则 $c{r}_D\left(H_{0,3}\cup B_4,v_6{y}_6\cup x_0{x}_6\right)=0$ ，由引理2可知路径 $u_0{v}_6{u}_5{v}_4$ 相交于 $H_{0,3}\cup B_4$ 产生一个交叉，路径 $v_0{u}_6{x}_6{x}_5{x}_4$ ， $y_0{y}_6{y}_5{v}_5{u}_4$ 相交于 $H_{0,3}\cup B_4$ 各产生两个交叉。由引理2可知 $u_0{v}_6{u}_5{v}_4$ 交叉于 $v_2{u}_3{x}_3$ ，则 $v_6$ 在区域 $R_5$ ， $R_8$ 或 $R_0$ 中，下面分为三种情形讨论。

情形1：若 $v_6$ 在区域 $R_5$ 中，由引理2可知 $u_0{v}_6{u}_5{v}_4$ 交叉于 $v_2{u}_3{x}_3$ ，则 $u_5$ 在区域 $R_8$ ， $R_5$ 或 $R_0$ 中。若 $u_5$ 在区域 $R_5$ 中，由引理2可知若 $v_4{u}_5$ 相交于 $v_2{u}_3$ ，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图7(a)。若 $v_4{u}_5$ 相交于 $x_3{u}_3$ ，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图7(b)。若 $u_5$ 在区域 $R_8$ 中，由引理2可知 $v_6{u}_5$ 相交于 $v_2{u}_3$ ，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图7(c)。若 $u_5$ 在区域 $R_0$ 中，由引理2可知 $v_6{u}_5$ 相交于 $x_3{u}_3$ ，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图7(d)。如图7所示，由 $c{r}_D\left(H_{0,3}\cup B_4,v_6{y}_6\right)=0$ 可知 $v_6{y}_6$ 干净，则 $y_6$ 在区域 $R_5$ 或 $R_9$ 中。由 $y_6$ 在区域 $R_5$ 或 $R_9$ 中，根据引理2可知路径 $y_0{y}_6{y}_5{v}_5{u}_4$ 都交于 $H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0$ 至少产生三个交叉。

(a) (b) (c) (d)

Figure 7. A good drawing of $H_{0,3}\cup B_4\cup u_0{v}_6{u}_5{v}_4$

图7. $H_{0,3}\cup B_4\cup u_0{v}_6{u}_5{v}_4$ 的一个好的画法

情形2：若 $v_6$ 在区域 $R_8$ 中，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图8(a)。如图8(a)所示，由于 $c{r}_D\left(H_{0,3}\cup B_4,x_0{x}_6\right)=0$ 可知 $x_0{x}_6$ 干净，则 $x_6$ 在区域 $R_2$ 或 $R_5$ 中。由 $x_6$ 在区域 $R_2$ 或 $R_5$ 中，根据引理2可知路径 $v_0{u}_6{x}_6{x}_5{x}_4$ 相交于 $H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0$ 至少产生三个交叉。

情形3：若 $v_6$ 在区域 $R_0$ 中，则 $D\left(H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0\right)$ 同构于图8(b)。如图8(b)所示，由于 $c{r}_D\left(H_{0,3}\cup B_4,x_0{x}_6\right)=0$ 可知 $x_0{x}_6$ 干净，则 $x_6$ 在区域 $R_2$ 或 $R_5$ 中。由 $x_6$ 在区域 $R_2$ 或 $R_5$ 中，根据引理2可知路径 $v_0{u}_6{x}_6{x}_5{x}_4$ 相交于 $H_{0,3}\cup B_4\cup v_4{u}_5{v}_6{u}_0$ 至少产生三个交叉。

(a) (b)

Figure 8. A good drawing of $H_{0,3}\cup B_4\cup u_0{v}_6{u}_5{v}_4$

图8. $H_{0,3}\cup B_4\cup u_0{v}_6{u}_5{v}_4$ 的一个好的画法

3. 结论

本文主要证明图DP(7,1)的交叉数，给出交叉数为7的一个好的画法。近一步通过反证法证明了交叉数的下界，最终证明了图DP(7,1)在 $l_0^D\ge 5$ ， $c{r}_D\left(C_0\right)=1$ 且 $c{r}_D\left(x_1{x}_2,u_0{v}_1\right)=1$ 下的交叉数为7。对于双广义Petersen图 $DP\left(2k+1,1\right)$ ， $\left(k\ge 3\right)$ ，证明了归纳基础 $c{r}_D\left(H_7\right)=7$ ，对于图 $DP\left(2k+1,1\right)$ ， $\left(k\ge 3\right)$ 交叉数将是下一步继续研究的内容。