玫瑰花窗图R3k+2(1,3)的交叉数

doi:10.12677/AAM.2024.132068

期刊菜单

玫瑰花窗图R_3k+2(1,3)的交叉数
The Crossing Number of Rose Windows Graph R_3k+2(1,3)

DOI: 10.12677/AAM.2024.132068, PDF, HTML, XML,
作者: 王爽：辽宁师范大学数学学院，辽宁大连
关键词: 玫瑰花窗图；交叉数；好的画法；Rose Windows Graph； Crossing Number； Good Drawing

摘要: 图论是离散数学的一个重要分支，是一门研究图的学问，而图的交叉数也是图论中的一个重要的研究方向，国内外诸多学者都对图的交叉数问题展开了相关研究。玫瑰花窗图是广义周期图的一类延伸，本文针对玫瑰花窗图的交叉数展开研究，给出了玫瑰花窗图R_3k+2(1,3)的相关定义，找到了R_3k+2(1,3)的一个好的画法，得到了R_3k+2(1,3)的交叉数的上界。最后利用数学归纳法和反证法得到了玫瑰花窗图R_3k+2(1,3)的交叉数的下界，进而完成了证明。

Abstract: Graph theory is an important branch of discrete mathematics, which is a study of graphs, and the crossing number of graphs is also an important research direction in graph theory. This paper studies the crossing number of the rose windows graph, gives the relevant definition of R_3k+2(1,3) the of the rose windows graph, finds a good drawing of R_3k+2(1,3) , and obtains the upper bound of the crossing number of R_3k+2(1,3) . Finally, the lower bound of the crossing number of the rose windows graph R_3k+2(1,3) is obtained by using the mathematical induction method and the counterproof method, and then the proof is completed.

文章引用：王爽. 玫瑰花窗图R_3k+2(1,3)的交叉数[J]. 应用数学进展, 2024, 13(2): 704-713. https://doi.org/10.12677/AAM.2024.132068

1. 引言

图的交叉数概念是Pual Turan根据其于1944年一个砖厂所碰到的实际难题提出的 [1] ，图的交叉数是图的一个重要参数，研究图的交叉数问题具有着重要的理论意义与现实意义，VLSI中的布线问题、草图的识别与重画问题、网络拓扑结构设计问题以及软件开发中的ER图的生成问题中都涉及图的交叉数的广泛应用。多年来，国内外许多学者都研究过图的交叉数问题，Garey和Johnson已经证明了确定一个图的交叉数是NP-完全问题 [2] 。正是由于其难度较大，故国内外在这方面的研究进展缓慢，研究对象也主要集中在一些具有特殊结构图的交叉数的具体数值或者研究其上界、下界和研究图的交叉数的一般性质上 [3] 。近些年来，诸多学者对一些特殊的图的交叉数进行了研究，并获得了相应的研究成果。

2003年，N.H. Nahas [4] 对当 $m, n$ 足够大时完全二部图的交叉数展开了进一步研究并得到了如下结果： $c r (K_{m, n}) \geq \frac{1}{5} m (m - 1) ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ + 9.9 \times 10^{- 6} m^{2} n^{2}$ 。2007年，梅汉飞和黄元秋 [5] 证明了 $K_{1, 5, n}$ 的交叉数，证明了 $c r (K_{1, 5, n}) = Z (6, n) + 4 ⌊ \frac{n}{2} ⌋$ 。此外，对于完全多部图，还有许多学者完成了许多图类交叉数的证明。2007年，黄元秋等人 [6] 研究了完全三部图 $K_{1, 4, n}$ 的交叉数，得到了 $c r (K_{1, 4, n}) = Z (5, n) + 2 ⌊ \frac{n}{2} ⌋$ 。紧接着，黄元秋等人 [7] [8] [9] 完成了完全三部图 $K_{1, 6, n}$ ， $K_{1, 8, n}$ 和 $K_{1, 10, n}$ 的交叉数的证明，得到了如下结果：

$c r (K_{1, 6, n}) = Z (7, n) + 6 ⌊ \frac{n}{2} ⌋$

$c r (K_{1, 8, n}) = Z (9, n) + 12 ⌊ \frac{n}{2} ⌋$

$c r (K_{1, 10, n}) = Z (11, n) + 20 ⌊ \frac{n}{2} ⌋$ .

除以上研究成果外，广义彼得森(Petersen)图的交叉数也深受交叉数方向的学者们的广泛关注。2004年，林晓惠 [10] 对 $P (4 k + 2, 2 k)$ 等部分广义Petersen图的交叉数进行了研究，得到了 $c r (P (4 k + 2, 2 k)) = 2 k + 1$ ， $c r (P (4 k + 2, 4)) = 2 k + 2$ 。2005年，马登举 [11] 等人证明了图 $P (2 m + 1, m)$ 的交叉数，证明得出了 $c r (P (2 k + 1, k)) = 3, k \geq 3$ 。郑百功 [12] 于2013年在硕士论文中证明了 $P (10, 3)$ 的交叉数。

实际上，广义Petersen图是一类广义周期图 [13] 。设G是一个简单图。G的一个分解是G的边不相交子图的列表，使得G的每条边都出现在列表中的一个子图中。如果对于每对整数i和j， $1 \leq i, j \leq t$ ，G存在一个自同构 $θ_{i, j}$ ，使得 $u v \in E (H_{i + l})$ 当且仅当 $θ_{i, j} (u) θ_{i, j} (v) \in E (H_{i + l})$ ，则称图G的一个分解 ${H_{1}, H_{2}, \dots, H_{t}}$ 是可传递的，其中下标取t的模。如果存在图G的一个传递分解，则称图G是广义周期图。

2. 玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的交叉数

2.1. 主要引理

设 ${H_{1}, H_{2}, \dots, H_{t}}$ 是图G的一个可传递分解。假设 $H_{i, j}$ 是 $H_{i}, H_{i + 1}, \dots, H_{j}$ 的并集，下标取模t。假设D是图G的一个好的画法。设c是一个正整数，对于 $1 \leq i \leq t$ ，若存在一个正整数 $l_{i}$ 满足 $f_{D} (H_{i, i - 1 + l_{i}}) \geq l_{i} c$ ，则令 $l_{c}^{D} (H_{i})$ 为 $l_{i}$ 的最小值使 $f_{D} (H_{i, i - 1 + l_{i}}) \geq l_{i} c$ ；若不存在这样的正整数 $l_{i}$ ，则令 $l_{c}^{D} (H_{i}) = t + 1$ 。

引理2.1 [13] ：设c为正实数，t和x为正整数。假设图G是具有可传递分解 ${H_{1}, H_{2}, \dots, H_{t}}$ 的广义周期图。则 $c r (G) \geq ⌈ c t ⌉$ 当且仅当在G的任意一种好画法D下有 $\max {l_{c}^{D} (H_{1}), l_{c}^{D} (H_{2}), \dots, l_{c}^{D} (H_{t})} \leq t$ 。

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

根据约当闭曲线定理，我们有以下引理。

引理2.2：在图G中，设C和C'是顶点集不相交的两个圈， $P_{k} = u_{1} u_{2} \dots u_{k}$ 是长度为k的路径且 $V (P_{k}) \cap V (C) = \emptyset$ 。假设D是图G的一个好的画法，则 $c r_{D} (C, C^{'})$ 是偶数，若 $u_{1}$ 、 $u_{k}$ 位于 $D (C)$ 的同一区域， $c r_{D} (P_{k}, C)$ 为偶数，否则就是奇数。

2.2. 玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的相关定义

所有在本文中没有明确定义的专业术语都可以在参考文献 [14] 中找到。

在广义Petersen图 $P (3 k + 2, 3)$ 的基础上添加一类边，得到玫瑰花窗图 $R_{3 k + 2} (1, 3)$ ，下面给出玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的具体定义。设玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的顶点集为 $V (R_{3 k + 2} (1, 3)) = {a_{i}, b_{i} | 1 \leq i \leq 3 k + 2}$ ，边集为 $E (R_{3 k + 2} (1, 3)) = {a_{i} a_{i + 1}, a_{i} b_{i}, b_{i} b_{i + 3}, b_{i} a_{i + 1}}$ ， $k \geq 2$ ，其中下标取模 $3 k + 2$ 。记玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的子集为 $E_{i}$ ，且有 $V (E_{i}) = {a_{i}, b_{i}, a_{i + 1}, b_{i + 3}}$ ， $E_{i} = {a_{i} a_{i + 1}, a_{i} b_{i}, b_{i} b_{i + 3}, b_{i} a_{i + 1}}$ ， $1 \leq i \leq 3 k + 2$ ， $k \geq 2$ ，可得 ${E_{1}, E_{2}, \dots, E_{3 k + 2}}$ 是 $R_{3 k + 2} (1, 3)$ 的一个可传递分解，其中 $E (R_{3 k + 2} (1, 3)) = \cup_{i = 1}^{3 k + 2} E_{i}$ 且 $E_{i} \cap E_{j} = \emptyset$ ， $i \neq j$ 。 $E_{i, j}$ 是 $E_{i}, E_{i + 1}, \dots, E_{j}$ 的并集，且 $f_{D} (H)$ 是H到所有非负实数集合的映射： $f_{D} (H) = c r_{D} (H) + c r_{D} (H, G \ E (H)) / 2$ 。图G在画法D下的交叉数用 $c r (D)$ 或 $c r_{D} (G)$ 表示。

另外，本文中定义路径：

$P_{0} = a_{1} a_{2} \dots a_{3 k + 2}$

$P_{1} = b_{1} b_{4} \dots b_{3 k + 1}$

$P_{2} = b_{2} b_{5} \dots b_{3 k + 2}$

$P_{3} = b_{3} b_{6} \dots b_{3 k}$

$P_{4} = a_{1} b_{1} a_{2} b_{2} \dots a_{3 k + 2} b_{3 k + 2}$

2.3. 归纳基础

引理2.3： $c r (R_{8} (1, 3)) = 6$ 。

2.4. $R_{3 k + 2} (1, 3)$ 的交叉数的上界

引理2.4： $c r (R_{3 k + 2} (1, 3)) \leq 2 k + 2$ ， $k \geq 2$ 。

证明：如图1所示，D是 $R (3 k + 2, 3, 1)$ 的一个好的画法，此时 $c r_{D} (R (3 k + 2, 3, 1)) = 2 k + 2$ ，根据交叉数的定义有 $c r (R_{3 k + 2} (1, 3)) \leq 2 k + 2$ 。

Figure 1. A good drawing of $R_{3 k + 2} (1, 3)$

图1. $R_{3 k + 2} (1, 3)$ 的一个好的画法

2.5. $R_{3 k + 2} (1, 3)$ 的交叉数的下界

引理2.5：(领结引理) 设 $1 \leq i \leq 3 k + 2$ ，D是 $B_{i}$ 的一个好画法且 $c r_{D} (B_{i}) = 1$ ，则 $a_{i + 1}$ 和 $b_{i}$ 被 $D (T_{i - 1})$ 分离或 $a_{i - 1}$ 和 $b_{i - 1}$ 被 $D (T_{i})$ 分离。

证明：假设 $a_{i + 1}$ 和 $b_{i}$ 在 $D (T_{i - 1})$ 划分平面的同一区域。如果 $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) \geq 1$ ，由引理2.2， $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) \geq 2$ ，与 $c r_{D} (B_{i}) = 1$ 相矛盾。因此 $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) = 0$ 。由 $c r_{D} (B_{i}) = 1$ ， $c r_{D} (b_{i} a_{i} a_{i + 1}, T_{i - 1}) = 1$ 。又由于D是好的画法，所以 $c r_{D} (a_{i - 1} b_{i - 1}, b_{i} a_{i} a_{i + 1}) = 1$ 。因此， $a_{i - 1}$ 和 $b_{i - 1}$ 被 $D (T_{i})$ 分离。

引理2.6：设D是 $R_{3 k + 2} (1, 3)$ 的一个好画法且 $c r_{D} (R_{3 k + 2} (1, 3)) < 2 k + 2$ ，若 $l_{1}^{D} \geq 4$ ，那么 $c r_{D} (T_{1}, T_{j}) = 0$ ， $3 \leq j \leq 3 k + 2$ ； $c r_{D} (B_{i}) = 0$ ， $2 \leq i \leq 3$ ； $c r_{D} (B_{3}, E_{1}) = 0$ 。

证明：由 $l_{1}^{D} \geq 4$ ，有 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ 。反证法。根据引理2.2，若 $c r_{D} (T_{1}, T_{j}) \geq 1$ ， $3 \leq j \leq 3 k + 2$ ，则 $c r_{D} (T_{1}, T_{j}) \geq 2$ ，与 $f_{D} (E_{1}) < 2 / 3$ 相矛盾，因此 $c r_{D} (T_{1}, T_{j}) = 0$ 。

假设 $c r_{D} (B_{2}) \geq 1$ ，由 $f_{D} (E_{1, 2}) < 4 / 3$ ，有 $c r_{D} (B_{2}) = 1$ ，由引理2.5，有 $a_{1}$ 、 $b_{1}$ 被 $D (T_{2})$ 分离或 $a_{3}$ 、 $b_{2}$ 被 $D (T_{1})$ 分离。根据引理2.2，若 $a_{1}$ 、 $b_{1}$ 被 $D (T_{2})$ 分离，有路径 $b_{1} b_{3} a_{4} P_{0} a_{3 k + 2} a_{1}$ 交 $T_{2}$ 。若 $a_{3}$ 、 $b_{2}$ 被 $D (T_{1})$ 分离，有路径 $a_{3} a_{4} a_{5} b_{5} b_{2}$ 交 $T_{1}$ 。两种情形均使 $f_{D} (E_{1, 2}) \geq 4 / 3$ ，矛盾。因此 $c r_{D} (B_{2}) = 0$ 。

假设 $c r_{D} (B_{3}) \geq 1$ ，由 $f_{D} (E_{1, 3}) < 2$ ，有 $c r_{D} (B_{3}) = 1$ 。根据引理2.5，有 $a_{2}$ 、 $b_{2}$ 被 $D (T_{3})$ 分离或 $a_{4}$ 、 $b_{3}$ 被 $D (T_{2})$ 分离。根据引理2.2，若 $a_{2}$ 、 $b_{2}$ 被 $D (T_{3})$ 分离，有路径 $b_{2} b_{5} a_{5} a_{4} a_{3} a_{2}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1} a_{2}$ 交 $T_{3}$ 。若 $a_{4}$ 、 $b_{3}$ 被 $D (T_{2})$ 分离，有路径 $b_{3} b_{6} a_{6} a_{5} a_{4}$ 、 $b_{3} b_{3 k + 2} P_{2} b_{5} a_{5} b_{4} a_{4}$ 交 $T_{2}$ ，两种情形均使 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾。因此 $c r_{D} (B_{3}) = 0$ 。

假设 $c r_{D} (B_{3}, E_{1}) \geq 1$ ，则有 $c r_{D} (T_{2}, E_{1}) \geq 1$ 或 $c r_{D} (T_{3}, E_{1}) \geq 1$ 。假设 $c r_{D} (T_{2}, E_{1}) \geq 1$ ，由 $f_{D} (E_{1, 2}) < 4 / 3$ ，有 $c r_{D} (T_{2}, E_{1}) = 1$ 。又由于 $c r_{D} (B_{2}) = 0$ ，则 $c r_{D} (T_{2}, b_{1} b_{4}) = 1$ ，根据引理2.2有路径 $b_{1} b_{3} a_{4} b_{4}$ 交 $T_{2}$ 使 $f_{D} (E_{1, 2}) \geq 4 / 3$ ，矛盾。因此 $c r_{D} (T_{2}, E_{1}) = 0$ 。假设 $c r_{D} (T_{3}, E_{1}) \geq 1$ ，由 $c r_{D} (T_{1}, T_{3}) = 0$ ，有 $c r_{D} (T_{3}, b_{1} b_{4}) \geq 1$ 且 $a_{1}$ 、 $b_{1}$ 位于 $D (T_{3})$ 划分平面的同一区域，又由于 $f_{D} (E_{1, 3}) < 2$ ，则 $c r_{D} (T_{3}, b_{1} b_{4}) = 1$ ，根据引理2.2有路径 $b_{1} b_{3 k} P_{3} b_{6} a_{7} b_{7} b_{4}$ 、 $a_{1} a_{3 k + 2} P_{0} a_{5} b_{4}$ 交 $T_{3}$ ，与 $f_{D} (E_{1, 3}) < 2$ 相矛盾。因此 $c r_{D} (T_{3}, E_{1}) = 0$ 。故 $c r_{D} (B_{3}, E_{1}) \geq 1$ 。

引理2.7：(画法引理) 假设D是使 $c r (R_{3 k + 2} (1, 3)) < 2 k + 2$ 的一个好的画法，已知 $c r (R_{3 (k - 1) + 2} (1, 3)) \geq 2 (k - 1) + 2$ ， $k \geq 3$ ，如果路径 $a_{i} b_{i} a_{i + 1} b_{i + 1} a_{i + 2} b_{i + 2} a_{i + 3}$ 上有a个交叉点，则在路径 $a_{i} a_{i + 1} a_{i + 2} a_{i + 3}$ 至少有 $a - 1$ 个交叉点， $a \geq 2$ ， $1 \leq i \leq 3 k + 2$ ；如果路径 $b_{i} a_{i + 1} b_{i + 1} a_{i + 2} b_{i + 2} a_{i + 3} b_{i + 3}$ 上有b个交叉点，则在路径 $b_{i} b_{i + 3}$ 至少有 $b - 1$ 个交叉点， $b \geq 2$ ， $1 \leq i \leq 3 k + 2$ 。

引理2.8：假设D是使 $c r (R_{3 k + 2} (1, 3)) < 2 k + 2$ 的一个好的画法，若 $l_{1}^{D} \geq 5$ ，则 $D (H_{1})$ 同构于图3。

证明：由 $l_{1}^{D} \geq 5$ ，有 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < 8 / 3$ 。由引理2.6知， $c r_{D} (B_{3}, E_{1}) = 0$ ， $c r_{D} (T_{1}, T_{j}) = 0$ ， $1 \leq j \leq 3 k + 2$ ，因此 $c r_{D} (a_{2} a_{3} a_{4} b_{4}, E_{1}) = 0$ ，且由好的画法的定义有 $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) \leq 1$ 。当 $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) = 1$ 时，即有 $c r_{D} (T_{2}, T_{4}) \geq 1$ ，根据引理2.2，此时 $c r_{D} (T_{2}, T_{4}) \geq 2$ ， $f_{D} (E_{1, 4}) \geq 2$ ， $D (H_{1})$ 同构于图2(a) 、图2(b)之一。

若 $D (H_{1})$ 同构于图2(a)，根据引理1有路径 $a_{1} a_{3 k + 2} P_{0} a_{6} b_{6} b_{3} a_{3}$ 、 $a_{1} b_{3 k + 2} P_{2} b_{5} a_{5} a_{4}$ 交 $a_{4} b_{4} b_{1} a_{2} a_{3}$ 使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾。若 $D (H_{1})$ 同构于图2(b)，由 $f_{D} (E_{1, 4}) < 8 / 3$ 有 $c r_{D} (a_{2} b_{2} a_{3}, H_{1} - a_{4} b_{4}) = 0$ ， $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) \leq 1$ ，若 $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) = 1$ ，根据引理2.7知 $a_{2} a_{3} a_{4} a_{5}$ 、 $b_{1} b_{4}$ 不干净，这与 $f_{D} (E_{1, 4}) < 8 / 3$ 相矛盾。所以 $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) = 0$ 且 $b_{2} \in R_{0}$ ， $D (H_{1} \cup T_{2})$ 同构于图2(c)，此时根据引理2.2有路径 $a_{1} a_{3 k + 2} P_{0} a_{4}$ 、 $a_{1} b_{3 k + 2} b_{3} a_{4}$ 交 $T_{2}$ 使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾。故 $D (H_{1})$ 同构于图3。

(a) (b) (c)

Figure 2. $D (H_{1})$ with $c r_{D} (H_{1}) = 1$

图2. $D (H_{1})$ 且 $c r_{D} (H_{1}) = 1$

Figure 3. $D (H_{1})$ with $c r_{D} (H_{1}) = 0$

图3. $D (H_{1})$ 且 $c r_{D} (H_{1}) = 0$

引理2.9：若 $D (H_{1})$ 同构于图3且 $b_{2} \in R_{2}$ ， $l_{1}^{D} \geq 5$ ，则 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5。

证明：由 $l_{1}^{D} \geq 5$ ，有 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < 8 / 3$ 。

当 $b_{2} \in R_{2}$ 时，有路径 $b_{2} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 交 $H_{1}$ 使 $f_{D} (E_{1, 4}) \geq 1$ ，由 $f_{D} (E_{1, 4}) < 8 / 3$ ，则 $c r_{D} (T_{2}, H_{1}) \leq 1$ ，根据引理2.6知 $c r_{D} (T_{2}, E_{1}) = 0$ ， $c r_{D} (B_{3}) = 0$ ，所以 $c r_{D} (T_{2}, a_{4} b_{4}) \leq 1$ 。若 $c r_{D} (T_{2}, a_{4} b_{4}) = 1$ 即 $c r_{D} (T_{2}, T_{4}) = 1$ ，根据引理2.2知 $c r_{D} (T_{2}, T_{4}) \geq 2$ ，这与 $f_{D} (E_{1, 4}) < 8 / 3$ 相矛盾，故有 $c r_{D} (T_{2}, H_{1}) = 0$ ， $D (H_{1} \cup T_{2})$ 同构于图4(a)。

由 $f_{D} (E_{1, 4}) < 8 / 3$ ，则 $c r_{D} (T_{3}, H_{1} \cup T_{2}) \leq 1$ ，根据引理2.6知 $c r_{D} (T_{3}, E_{1}) = 0$ ， $c r_{D} (B_{3}) = 0$ ，则有 $c r_{D} (T_{3}, a_{4} b_{4}) \leq 1$ 。若 $c r_{D} (T_{3}, a_{4} b_{4}) = 1$ 即 $c r_{D} (B_{4}) = 1$ ，由引理2.5，有 $a_{3}$ 、 $b_{3}$ 被 $T_{4}$ 分离或 $a_{5}$ 、 $b_{4}$ 被 $T_{3}$ 分离。当 $a_{3}$ 、 $b_{3}$ 被 $T_{4}$ 分离时，此时 $f_{D} (E_{1, 4}) \geq 2$ ，则 $c r_{D} (T_{2}, T_{4}) = 0$ ， $c r_{D} (T_{4}, E_{1}) = 0$ ，故 $a_{3}$ 、 $b_{1}$ 在 $T_{4}$ 划分平面的同一区域，根据引理2.2有路径 $b_{1} b_{3 k} P_{3} b_{3}$ 交 $T_{4}$ 使 $f_{D} (E_{1, 4}) \geq 5 / 2$ ，由 $f_{D} (E_{1, 4}) < 8 / 3$ ，有 $c r_{D} (b_{2} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ，故知 $b_{5}$ 、 $b_{3}$ 被 $T_{4}$ 分离，根据引理2.2有路径 $b_{5} a_{6} P_{0} a_{3 k + 2} b_{3 k + 2} b_{3}$ 交 $T_{4}$ 使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。当 $a_{5}$ 、 $b_{4}$ 被 $T_{3}$ 分离时，同理有路径 $a_{5} b_{5} a_{6} a_{7} b_{7} b_{4}$ 交 $T_{3}$ 使 $f_{D} (E_{1, 4}) \geq 5 / 2$ ，由 $c r_{D} (T_{3}, E_{1}) = 0$ 知 $b_{4}$ 、 $b_{1}$ 在 $T_{3}$ 划分平面的同一区域，所以 $a_{5}$ 、 $b_{1}$ 被 $T_{3}$ 分离，即有路径 $b_{1} b_{3 k} P_{3} b_{6} a_{6} a_{5}$ 交 $T_{3}$ 使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。因此 $c r_{D} (T_{3}, a_{4} b_{4}) = 0$ 即 $c r_{D} (B_{4}) = 0$ 。

对于 $T_{4}$ ，同理有 $c r_{D} (T_{4}, H_{1} \cup B_{3}) \leq 1$ ，又知 $c r_{D} (B_{2}, T_{4}) = 0$ ， $c r_{D} (B_{4}) = 0$ ，则 $c r_{D} (T_{4}, b_{1} b_{4}) \leq 1$ 。当 $c r_{D} (T_{4}, b_{1} b_{4}) = 1$ 时，根据好的画法的定义有 $c r_{D} (a_{4} a_{5}, b_{1} b_{4}) = 1$ ，此时 $f_{D} (E_{1, 4}) \geq 2$ ， $a_{5} \in R_{2} \cup R_{0}$ ， $f_{D} (E_{1}) \geq 1 / 2$ ，由 $f_{D} (E_{1}) < 2 / 3$ 、 $f_{D} (E_{1, 2}) < 4 / 3$ 知路径 $b_{2} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 中至少有一条路径交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 5 / 2$ 。当 $a_{5} \in R_{0}$ 时，由 $f_{D} (E_{1, 4}) < 8 / 3$ ，有 $c r_{D} (b_{2} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ，则 $b_{5} \in R_{2} \cup R_{3}$ ，均会与 $a_{5}$ 分离，根据引理2.2有 $a_{5} b_{5}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。当 $a_{5} \in R_{2}$ 时， $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图4(b)，根据引理2.2有路径 $a_{5} P_{0} a_{3 k + 2} a_{1}$ 、 $a_{5} b_{5} P_{2} b_{3 k + 2} a_{1}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 2$ ，由 $f_{D} (E_{1}) < 2 / 3$ 、 $f_{D} (E_{1, 2}) < 4 / 3$ 知路径 $a_{5} P_{0} a_{3 k + 2} a_{1}$ 、 $a_{5} b_{5} P_{2} b_{3 k + 2} a_{1}$ 各交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。因此 $c r_{D} (T_{4}, b_{1} b_{4}) = 0$ 即 $c r_{D} (T_{4}, H_{1} \cup B_{3}) \leq 0$ 。

综上知 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5。

(a) (b)

Figure 4. Subdrawings of D

图4. D的子画法

(a) (b) (c)

Figure 5. Subdrawings of D

图5. D的子画法

引理2.10：若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5，则 $l_{1}^{D} \leq 5$ 。

证明：假设 $l_{1}^{D} \geq 6$ ，则 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < 8 / 3$ ， $f_{D} (E_{1, 5}) < 10 / 3$ 。

根据引理2.2，当 $b_{5} \in R_{1}$ 时，有 $c r_{D} (b_{2} b_{5} a_{5}, T_{1}) \geq 2$ ，这与 $f_{D} (E_{1}) < 1$ 相矛盾。当 $b_{5} \in R_{2}$ 时，有路径 $b_{5} a_{5}$ 、 $b_{5} a_{6} b_{6} b_{3}$ 、 $b_{5} b_{8} a_{8} P_{0} a_{5}$ 交 $T_{2}$ 使 $f_{D} (E_{1, 2}) \geq 3 / 2$ ，矛盾。当 $b_{5} \in R_{3}$ 时，有 $b_{2} b_{5}$ 、 $b_{5} a_{5}$ 以及路径 $b_{5} a_{6} a_{5}$ 交 $T_{3}$ 使 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾。当 $b_{5} \in R_{4}$ 时， $c r_{D} (b_{2} b_{5}, T_{4}) \geq 1$ ，且有路径 $b_{5} a_{5} P_{0} a_{3 k + 2} b_{3 k + 2} a_{1}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} b_{6} b_{3}$ 、 $b_{5} P_{2} b_{3 k - 1} a_{3 k} b_{3 k} b_{1}$ 交 $T_{4}$ 使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。

当 $b_{5} \in R_{5}$ 时，根据引理2.2有路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 交 $b_{1} b_{4} a_{4} a_{3} a_{2} b_{1}$ 使 $f_{D} (E_{1, 4}) \geq 1$ ，由 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ 知路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 中至少有一条路径交 $B_{4}$ 至少两次，此时有 $f_{D} (E_{1, 4}) \geq 3 / 2$ 。

若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(a)，由引理2.2，若此时 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) \geq 1$ ，必有 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) \geq 2$ ，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾，因此 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ， $D (H_{1, 2} \cup B_{4})$ 同构于图6(a)。根据引理2.2，此时又有路径 $b_{3} P_{3} b_{3 k} b_{1}$ 、 $b_{3} b_{3 k + 2} a_{3 k + 2} b_{3 k + 1} P_{1} b_{4}$ 交 $b_{5} a_{5} a_{4} a_{3} b_{2} b_{5}$ 使 $f_{D} (E_{1, 5}) \geq 5 / 2$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ 知 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) \leq 1$ ，则 $b_{6} \notin R_{1}$ 。当 $b_{6} \in R_{0} \cup R_{2} \cup R_{4}$ 时， $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) = 1$ ， $f_{D} (E_{1, 5}) \geq 3$ ，则 $c r_{D} (b_{5} a_{6}, H_{1, 2} \cup B_{4}) = 0$ ， $a_{6} \in R_{5} \cup R_{6}$ ，根据引理2.2知路径 $b_{6} a_{6}$ 交 $H_{1, 2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 7 / 2$ ，矛盾。当 $b_{6} \in R_{5}$ 时， $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) = 1$ ， $f_{D} (E_{1, 5}) \geq 3$ ，根据引理2.2，此时有 $c r_{D} (b_{3} b_{6}, b_{2} b_{5} a_{5}) = 1$ 。若 $c r_{D} (b_{3} b_{6}, b_{2} b_{5}) = 1$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ 知 $c r_{D} (b_{6} a_{6} a_{5}, H_{1, 2} \cup B_{4}) = 0$ ，即 $c r_{D} (b_{2} b_{5}, b_{3} a_{4} a_{5} a_{6} b_{6} b_{3}) = 1$ ，则路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 必交 $a_{6} b_{6}$ ，根据引理2.7知 $b_{4} b_{7}$ 不干净，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾。若 $c r_{D} (b_{3} b_{6}, a_{5} b_{5}) = 1$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ ，路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 必有一条路径交 $b_{4} b_{1} a_{2}$ ，另一条路径交 $B_{4}$ ， $f_{D} (E_{1, 3}) \geq 1$ ，根据引理2.2知，这条交 $B_{4}$ 的路径若交 $T_{3}$ 至少两次使 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾，因此这条路径必交 $T_{4}$ ，即必交 $a_{4} b_{4}$ ，根据引理2.7知 $b_{3} b_{6}$ 在删除边 $a_{5} b_{5}$ 的情况下仍不干净，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾。当 $b_{6} \in R_{3}$ 时，若 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) \geq 1$ ，根据引理2.2必有 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) \geq 2$ ，矛盾，因此 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) = 0$ ，此时又有路径 $b_{6} a_{6} a_{5}$ 、 $b_{6} a_{7} b_{7} P_{1} b_{3 k + 1} b_{2}$ 交 $T_{3}$ 使 $f_{D} (E_{1, 5}) \geq 10 / 3$ ，矛盾。当 $b_{6} \in R_{6}$ 时，同理知 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) = 0$ ，根据引理2.2，有路径 $b_{6} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $b_{6} P_{3} b_{3 k} a_{3 k + 1} b_{3 k + 1} a_{3 k + 2} b_{3 k + 2} a_{1}$ 、 $b_{6} a_{7} b_{7} b_{4}$ 、 $b_{3} b_{3 k + 2} b_{3 k - 1} a_{k} b_{3 k} b_{1}$ 交 $H_{1, 2} \cup B_{4}$ ，且路径 $b_{6} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $b_{6} P_{3} b_{3 k} a_{3 k + 1} b_{3 k + 1} a_{3 k + 2} b_{3 k + 2} a_{1}$ 均交 $H_{1, 2} \cup B_{4}$ 至少两次使 $f_{D} (E_{1, 5}) \geq 3$ ，由 $f_{D} (E_{1, 4}) < 8 / 3$ ，这四条路径中至少有一条路径交 $a_{5} b_{5}$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ 知 $c r_{D} (b_{4} b_{7}, H_{1, 2} \cup B_{4}) = 0$ ，则 $b_{7} \in R_{0} \cup R_{4} \cup R_{5}$ ，与 $b_{6}$ 分离，即路径 $b_{6} a_{7} b_{7}$ 不干净。若 $c r_{D} (b_{6} a_{7} b_{7}, a_{5} b_{5}) \geq 1$ ，根据引理2.7知 $a_{4} b_{4} a_{5} b_{5}$ 不能再产生交叉，否则 $b_{3} b_{6}$ 不干净，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾，因此路径 $b_{6} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $b_{6} P_{3} b_{3 k} a_{3 k + 1} b_{3 k + 1} a_{3 k + 2} b_{3 k + 2} a_{1}$ 均交 $E_{1, 3}$ 中的边至少两次，此时 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾。若 $c r_{D} (b_{6} a_{7} b_{7}, a_{5} b_{5}) = 0$ ，根据引理2.7知 $b_{4} b_{7}$ 不干净，矛盾。

若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(b)，根据引理2.2有路径 $b_{5} a_{5}$ 、 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $a_{5} a_{6} b_{6} b_{3}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 5 / 2$ 。若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(d)，根据引理2.2有路径 $b_{5} a_{5}$ 、 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} b_{3 k + 2} b_{3}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 5 / 2$ 。由 $f_{D} (E_{1}) < 2 / 3$ 、 $f_{D} (E_{1, 2}) < 4 / 3$ 知路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 中至少有一条路径交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 5}) \geq 3$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ ， $c r_{D} (a_{5} a_{6}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ，即 $a_{6} \in R_{4} \cup R_{0}$ ，故 $b_{5}$ 与 $a_{6}$ 分离，因此有 $c r_{D} (b_{5} a_{6}, H_{1} \cup T_{2} \cup B_{4}) \geq 1$ ，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾。

若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(c)，根据引理2.2有路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 、 $a_{5} a_{6} b_{6} b_{3}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} b_{3 k + 2} b_{3}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 2$ ，同图6(b)知路径 $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 中至少有一条路径交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 5 / 2$ ，由 $f_{D} (E_{1, 4}) < 8 / 3$ ，有 $c r_{D} (b_{3} b_{6}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ，故 $b_{6} \in R_{3} \cup R_{0}$ ，当 $b_{6} \in R_{3}$ 时，由引理2.2有路径 $b_{6} P_{3} b_{3 k} b_{1}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。当 $b_{6} \in R_{0}$ 时，由 $f_{D} (E_{1, 5}) < 10 / 3$ ， $c r_{D} (b_{5} a_{6} a_{5}, H_{1} \cup T_{2} \cup B_{4}) \leq 1$ ，所以 $a_{6} \in R_{4} \cup R_{5}$ 。当 $a_{6} \in R_{4}$ 时，有 $c r_{D} (b_{5} a_{6} b_{6}, H_{1} \cup T_{2} \cup B_{4}) \geq 2$ ，根据引理2.7知 $b_{3} b_{6}$ 不干净， $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。当 $a_{6} \in R_{5}$ 时，若 $c r_{D} (a_{6} b_{6}, b_{1} b_{4}) \geq 1$ ， $b_{5} P_{2} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} P_{0} a_{3 k + 2} a_{1}$ 两条路径均交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾，所以 $c r_{D} (a_{6} b_{6}, b_{1} b_{4}) = 0$ ，根据引理2.2知， $c r_{D} (a_{6} b_{6}, H_{1} \cup T_{2} \cup B_{4}) \geq 2$ ，这与 $f_{D} (E_{1, 4}) < 8 / 3$ 相矛盾。

当 $b_{5} \in R_{0}$ 时，若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(a)，此时有 $b_{2} b_{5}$ 、 $a_{5} b_{5}$ 路径 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 、 $b_{3} b_{3 k + 2} a_{1}$ 、 $b_{5} a_{6} a_{5}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾。若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(b)、图5(c)，已知有路径 $b_{2} b_{5}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 、 $a_{5} a_{6} b_{6} b_{3}$ 、 $a_{5} b_{5} a_{6} P_{0} a_{3 k + 2} b_{3 k + 2} b_{3}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 5 / 2$ ，此时 $c r_{D} (b_{2} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 1$ ，而 $b_{2}$ 、 $b_{5}$ 位于 $T_{1} \cup B_{4}$ 划分平面的同一区域，根据引理2.2，若 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) \geq 1$ ，则有 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) \geq 2$ ，矛盾，因此 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) = 0$ ，故有 $c r_{D} (b_{2} b_{5}, a_{2} a_{3} \cup b_{1} b_{4}) = 1$ ，由 $f_{D} (E_{1, 2}) < 4 / 3$ 知 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 必交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 3$ ，矛盾。若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(d)，由引理2.2有路径 $b_{2} b_{5}$ 、 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 交 $H_{1} \cup T_{2} \cup B_{4}$ 使 $f_{D} (E_{1, 4}) \geq 3 / 2$ ，同图5(b)、图5(c)情况类似，若 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) \geq 1$ ，则有 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) \geq 2$ ， $f_{D} (E_{1, 4}) \geq 5 / 2$ ， $f_{D} (E_{1, 2}) \geq 1$ ，由 $f_{D} (E_{1, 2}) < 4 / 4$ 知 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 必交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾，因此若 $c r_{D} (b_{2} b_{5}, T_{1} \cup B_{4}) = 0$ ，所以有 $c r_{D} (b_{2} b_{5}, a_{2} a_{3} \cup b_{1} b_{4}) = 1$ ，同理由 $f_{D} (E_{1, 2}) < 4 / 3$ 知 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 必交 $B_{4}$ 至少两次使 $f_{D} (E_{1, 4}) \geq 2$ ，根据引理2.2，若 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) \geq 1$ ，必有 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) \geq 2$ ，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾，因此 $c r_{D} (a_{5} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ， $D (H_{1, 2} \cup B_{4})$ 同构于图6(b)、图6(c)之一。若 $D (H_{1, 2} \cup B_{4})$ 同构于图6(b)，由引理2.2有路径 $b_{3} b_{3 k + 2} a_{1}$ 、 $b_{3} b_{6} a_{7} b_{7} b_{4}$ 交 $H_{1, 2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 3$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ ，知 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup B_{4}) = 0$ ，且路径 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 不能交 $H_{1, 2} \cup B_{4}$ 三次，故其必交 $a_{4} b_{4} a_{5}$ ，根据引理2.7知 $b_{3} b_{6}$ 不干净，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾。若 $D (H_{1, 2} \cup B_{4})$ 同构于图6(c)，由引理2.2有路径 $b_{3} b_{6} a_{7} b_{7} b_{4}$ 交 $H_{1, 2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 5 / 2$ ，由 $f_{D} (E_{1, 4}) < 8 / 3$ ， $f_{D} (E_{1, 5}) < 10 / 3$ 知 $c r_{D} (b_{4} b_{7}, H_{1} \cup T_{2} \cup B_{4} \cup b_{2} b_{5}) = 0$ 、 $c r_{D} (b_{4} b_{7}, a_{5} b_{5}) \leq 1$ ，故 $b_{7} \in R_{4} \cup R_{6} \cup R_{7} \cup R_{0}$ 。当 $b_{7} \in R_{4} \cup R_{6}$ 时，有路径 $b_{7} P_{1} b_{3 k + 1} a_{3 k + 1} a_{3 k} b_{3 k} b_{1}$ 、 $b_{7} a_{7} b_{6} b_{3}$ 交 $H_{1} \cup T_{2} \cup B_{4} \cup b_{2} b_{5}$ 使 $f_{D} (E_{1, 4}) \geq 8 / 3$ ，矛盾。当 $b_{7} \in R_{7}$ 时，有路径 $b_{7} P_{1} b_{3 k + 1} a_{3 k + 1} a_{3 k} b_{3 k} b_{1}$ 、 $b_{7} a_{7} b_{6} b_{3}$ 、 $b_{7} a_{8} b_{8} P_{2} b_{3 k + 2} b_{3}$ 交 $H_{1, 2} \cup B_{4}$ 使 $f_{D} (E_{1, 5}) \geq 10 / 3$ ，矛盾。当 $b_{7} \in R_{0}$ 时，有 $c r_{D} (b_{4} b_{7}, a_{5} b_{5}) = 1$ ， $f_{D} (E_{1, 5}) \geq 3$ ，对于路径 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ ，若其交 $a_{3} a_{4}$ ，必交 $T_{3}$ 至少两次使 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾，所以路径 $b_{2} b_{3 k + 1} a_{3 k + 2} a_{1}$ 必交 $a_{4} b_{4}$ ，根据引理2.7知 $b_{3} b_{6}$ 不干净，这与 $f_{D} (E_{1, 5}) < 10 / 3$ 相矛盾。

(a) (b) (c)

Figure 6. Subdrawings of D

图6. D的子画法

引理2.11：设D是 $R_{3 k + 2} (1, 3)$ 的一个好画法使得 $c r (R_{3 k + 2} (1, 3)) < 2 k + 2$ ，且 $c r (R_{3 (k - 1) + 2} (1, 3)) \geq 2 (k - 1) + 2$ ， $k \geq 2$ 。若 $D (H_{1})$ 同构于图3且 $b_{2}$ 在区域 $R_{0}$ ，则 $l_{1}^{D} \leq 12$ 。

证明：假设 $l_{1}^{D} \geq 13$ ，则 $f_{D} (E_{1}) < 2 / 3$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < 8 / 3$ ， $f_{D} (E_{1, 5}) < 10 / 3$ ， $f_{D} (E_{1, 6}) < 4$ ， $f_{D} (E_{1, 7}) < 14 / 3$ ， $f_{D} (E_{1, 8}) < 16 / 3$ ， $f_{D} (E_{1, 9}) < 6$ ， $f_{D} (E_{1, 10}) < 20 / 3$ ， $f_{D} (E_{1, 11}) < 22 / 3$ ， $f_{D} (E_{1, 12}) < 8$ 。

由 $l_{1}^{D} \geq 6$ 且 $b_{2}$ 在区域 $R_{0}$ ，结合以上定理可以类似的证明出 $c r_{D} (B_{3}, H_{1}) = 0$ 且 $b_{3}$ 在区域 $R_{0}$ 中， $D (H_{1} \cup B_{3})$ 同构于图7(a)。同时利用反证法可以证得 $b_{5}$ ， $a_{5}$ 在区域 $R_{0}$ 中且 $c r_{D} (b_{2} b_{5} a_{5} a_{4}, H_{1} \cup B_{3}) = 0$ ， $D (H_{1, 2} \cup T_{3})$ 同构于图7(b)。接下来，在 $H_{1, 2} \cup T_{3}$ 添加路径 $b_{3} b_{6} a_{6} a_{5}$ ，通过对 $b_{6}$ 可能存在的区域进行分类讨论。当 $b_{6}$ 在区域 $R_{1}$ ， $R_{2}$ ， $R_{3}$ ， $R_{4}$ ， $R_{5}$ 中时，都可以通过前六组的计数假设得出矛盾。

当 $b_{6}$ 在区域 $R_{0}$ 中时，由 $f_{D} (E_{1, 5}) < 10 / 3$ 知 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup T_{3}) \leq 2$ ，根据引理2.2，若 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup T_{3}) \geq 1$ ，则 $c r_{D} (b_{3} b_{6}, H_{1} \cup B_{2})$ 为偶数， $c r_{D} (b_{3} b_{6}, a_{3} a_{4} a_{5} b_{5} b_{2} a_{3})$ 为奇数，由 $f_{D} (E_{1, 3}) < 2$ ，有 $c r_{D} (b_{3} b_{6}, B_{2}) = 0$ 且 $b_{3} b_{6}$ 不同时交 $a_{3} a_{4}$ 、 $b_{1} b_{4}$ ，则当 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup T_{3}) = 2$ 时，必有 $c r_{D} (b_{3} b_{6}, a_{3} a_{4} b_{4}) = 2$ ，由 $f_{D} (E_{1, 5}) < 10 / 3$ ，有 $c r_{D} (b_{4} a_{5}, H_{1, 2} \cup T_{3}) = 0$ ，此时 $D (H_{1, 2} \cup B_{4} \cup b_{3} b_{6})$ 同构于图7(c)，根据引理2.2，有路径 $b_{6} P_{3} b_{3 k} b_{1}$ 、 $b_{6} a_{7} P_{0} a_{3 k + 2} a_{1}$ 交 $T_{4}$ 使 $f_{D} (E_{1, 5}) \geq 10 / 3$ ，矛盾。所以 $c r_{D} (b_{3} b_{6}, H_{1, 2} \cup T_{3}) = 1$ 即 $c r_{D} (b_{3} b_{6}, a_{4} a_{5} b_{5} b_{2}) = 1$ ， $D (H_{1, 2} \cup T_{3} \cup b_{3} b_{6})$ 同构于图7(d)~(f)之一。而当 $D (H_{1, 2} \cup T_{3} \cup b_{3} b_{6})$ 同构于图7(d)~(f)之一时，结合以上引理，以及针对前12组边的计数假设，讨论可能出现的所有子情况，最终得出矛盾，证毕。

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

Figure 7. Subdrawings of D

图7. D的子画法

3. 结论

本文利用数学归纳法和反证法证明了玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的交叉数。首先找到了玫瑰花窗图 $R_{3 k + 2} (1, 3)$ 的一个好的画法，根据交叉数的定义验证了 $c r (R_{3 k + 2} (1, 3)) \leq 2 k + 2$ 。随后将 $R_{3 k + 2} (1, 3)$ 的边集分成 $3 k + 2$ 组，得到了一个 $R_{3 k + 2} (1, 3)$ 的一个可传递分解。文中枚举所有可能的情况与画法，分类讨论，根据相关引理以及限制条件，最终验证了 $R_{3 k + 2} (1, 3)$ 的交叉数的下界，即 $c r (R_{3 k + 2} (1, 3)) \leq 2 k + 2$ 。进而证明了 $c r (R_{3 k + 2} (1, 3)) = 2 k + 2$ 。

参考文献

[1]	Turan, P. (1997) A Note of Welcome. Journal of Graph Theory, 1, 7-9. https://doi.org/10.1002/jgt.3190010105
[2]	Garey, M.R. and Johnson, D.S. (1993) Crossing Number Is NP-Complete. SIAM Journal on Algebraic & Discrete Methods, 1, 312-316. https://doi.org/10.1137/0604033
[3]	黄元秋, 王晶. 图的交叉数综述[J]. 华东师范大学学报(自然科学版), 2010(3): 68-80.
[4]	Nahas, N. (2003) On the Crossing Number of Km, N. The Electronic Journal of Combinatorics, 10, 1-6. https://doi.org/10.37236/1748
[5]	Mei, H.F. and Huang, Y.Q. (2007) The Crossing Number of Ki5, N. Interna-tional Journal of Mathematical Combinatorics, 1, 33-44.
[6]	Huang, Y. and Zhao, T. (2007) The Crossing Number of . Journal of Natural Science of Hunan Normal University, 308, 1634-1638. https://doi.org/10.1016/j.disc.2006.12.002
[7]	黄元秋, 赵霆雷. 关于完全3-部图的交叉数[J]. 应用数学学报, 2006, 29(6): 1046-1053.
[8]	Huang, Y.Q. and Zhao, T.L. (2006) On the Crossing Number of the Complete Tri-partite Graph . Acta Mathematica Scientia, 26, 1115-1122.
[9]	王晶, 黄元秋. 完全3-部图的交叉数[J]. 高校应用数学学报A辑, 2008, 23(3): 349-356.
[10]	林晓惠. 图论中若干难题的研究[D]: [博士学位论文]. 大连: 大连理工大学, 2004.
[11]	马登举, 任韩, 卢俊杰. 广义Petersen图G(2m+1, M)的交叉数[J]. 华东师范大学学报(自然科学版), 2005(1): 34-39.
[12]	郑百功. 冒泡排序图和广义Petersen图P(10, 3)的交叉数[D]: [硕士学位论文]. 大连: 大连理工大学, 2013.
[13]	Yang, X., Chen, X. and Yang, Y. (2023) A Necessary and Sufficient Condition for Lower Bounds on Crossing Numbers of Generalized Periodic Graphs in an Arbitrary Surface.
[14]	Bondy, J. and Murty, U. (1976) Graph Theory with Its Applications. American Elsevier, New York. https://doi.org/10.1007/978-1-349-03521-2

为你推荐

友情链接