设为首页 加入收藏 期刊导航 网站地图

Pure Mathematics
Vol. 13  No. 10 ( 2023 ), Article ID: 74643 , 7 pages
10.12677/PM.2023.1310319

一类小阶图的交叉数

鲁东岳

辽宁师范大学数学学院，辽宁 大连

收稿日期：2023年9月19日；录用日期：2023年10月20日；发布日期：2023年10月31日

摘要

图的交叉数的研究已经有几十年的历史，Garey和Johnson证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。本文令cr(G)表示图G的交叉数，主要利用循环图C(16, 4)的一个分解{F1, F2, F12}对其交叉数进行研究。首先给出C(16, 4)交叉数为8的好的画法，得到交叉数的上界。然后采用反证法，将C(16, 4)的边集分成边不相交的3组，讨论所有可能情况，从而证得C(16, 4)的交叉数的下界。

关键词

交叉数，循环图，好的画法

The Crossing Number of a Class of Small-Order Graphs

Dongyue Lu

School of Mathematics, Liaoning Normal University, Dalian Liaoning

Received: Sep. 19th, 2023; accepted: Oct. 20th, 2023; published: Oct. 31st, 2023

ABSTRACT

Cross numbers of graphs have been studied for decades, Garey and Johnson demonstrated that determining the cross numbers of a graph is an NP-complete problem. Because of the difficulty of proof, the research on the cross number of graphs at home and abroad is slow. In this paper, the cross number of a graph G is represented cr(G), and the cross number is studied by using a decomposition C(16, 4) of a cyclic graph C(16, 4). First of all, a good drawing of the cross number of 8 is given, and the upper bound of the cross number is obtained. Then we divide the edge set of C(16, 4) into 3 groups with disjoint edges, discuss all possible cases, and obtain the lower bound of the cross number.

Keywords:Crossing Number, Cyclic Graphs, Good Drawing

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图的交叉数问题的研究，起源于20世纪40年代砖厂遇到的难题。据说第二次世界大战时期，Turan [1] 发现运砖车沿铁轨向仓库运砖时，车很容易在铁轨交点的位置脱节。他因此想到通过减少铁轨交叉个数来降低损失的方法，交叉数的概念由此而来。

关于图的交叉数的研究已经有几十年的历史，Garey和Johnson [2] 证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。只得到了较少图的交叉数的精确值和一些具有特殊结构的图的交叉数的上下界。主要研究结果有：1960年，Guy [3] 对完全图 K n 的交叉数提出猜想：对于任意的 n ≥ 1 ，有

c r ( K n ) = Z ( n ) = 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ .

其中 ⌊ x ⌋ 表示不超过任意实数x的最大整数。1969年，Guy在文献 [4] 中验证了当 n ≤ 10 时，猜想成立。1970年，Kleitman在文献 [5] 中给出了当n足够大时， K n 交叉数的下界：

c r ( K n ) ≥ n ( n − 1 ) ( n − 2 ) ( n − 3 ) / 80 .

Richter等 [6] [7] 证明了 K n − 1 和 K n 之间的关系： c r ( K n ) ≥ ⌈ n n − 4 ⋅ c r ( K n − 1 ) ⌉ 。2019年，Balogh [8] 给出了完全图 K n 的下界为 lim n → ∞ c r ( K n ) 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ ≥ 0.985 ，这是当前最优的结论。

设A，B，C为图G的边集的互不相交的子集 [9] ，则对于图G的任意画法D，有

c r D ( A ∪ B ) = c r D ( A ) + c r D ( B ) + c r D ( A , B ) ,

c r D ( A ∪ B , C ) = c r D ( A , C ) + c r D ( B , C ) .

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

根据Jordan曲线定理，我们有以下引理。

引理1 在图G中，设C和 C ′ 是两个顶点不相交的圈， P t = u 1 u 2 ⋯ u t 是一条t阶路径且 V ( P t ) ∩ V ( C ) = ϕ 。假设D是G的一个好的画法，那么 c r D ( C , C ′ ) 是偶数；当 u 1 和 u t 位于 D ( C ) 的同一区域时， c r D ( C , P t ) 为偶数，否则为奇数。

2. 循环图C(16, 4)的交叉数

2.1. 循环图C(16, 4)的定义

循环图C(16, 4)的顶点集 V = { v i | 0 ≤ i ≤ 15 } ，边集 E = { ( v i , v i + 1 ) , ( v i , v i + 4 ) | 0 ≤ i ≤ 15 } ，顶点标号i取模 v i ，为了后续书写方便，用i表示 v i ， ( i , i + 1 ) 和 ( i , i + 4 ) 分别表示 ( v i , v i + 1 ) 和 ( v i , v i + 4 ) 。

2.2. 循环图C(16, 4)的交叉数的上界

引理2 c r ( C ( 16 , 4 ) ) ≤ 8

证明：图1给出了 C ( 16 , 4 ) 的一个有8个交叉点的好的画法，因此 c r ( C ( 16 , 4 ) ) ≤ 8 。

Figure 1. Good drawings of C(16, 4)

图1. C(16, 4)的好的画法

2.3. 循环图C(16, 4)的交叉数的下界

引理3 令D是 Q 3 的一个好画法，并且 C r ( D ) = 3 ，对于D的一个区域R的边界 ∂ ( R ) ， | ∂ ( R ) ∩ V ( Q 3 ) | = 8 的画法不存在。

证明：反证法，假设画法D存在。由 C r ( D ) = 3 ，可以得到4种情形，即8圈不自交，自交1次，自交2次，自交3次。画法D见图2。

情形1 8圈 M 21 不自交。8圈不自交时，8圈 M 21 的画法 D 1 为平面嵌入，在同构意义下，只有一种，见图3。记 M 22 = { 5 − 1 , 9 − 13 , 0 − 12 , 4 − 8 } ，讨论将 M 22 中4条边全部添入8圈 M 21 后，产生交叉的所有情况。此时 M 22 中4条边等价，不失一般性，假设边 5 − 1 不产生交叉，则有2种画法且这2种画法同构，那么添入边 5 − 1 时，画法唯一。当前画法下，边 4 − 8 与边 0 − 12 等价，不失一般性，设 C r D ( 4 − 8 ) ≤ C r D ( 0 − 12 ) 。此时 C r D ( 5 − 1 ) = 0 ，则 C r D ( 4 − 8 ) = { 0 , 1 } 。当 C r D ( 4 − 8 ) = 0 时，画法唯一，添入后，分离3度点，矛盾。当 C r D ( 4 − 8 ) = 1 时，根据好的画法的定义，相邻边不能交。若边 4 − 8 交边 5 − 9 一次，分离3度点，矛盾。若边 4 − 8 交路径 0 − 1 − 13 − 12 一次，分离3度点，矛盾。因此边 4 − 8 只能交边 5 − 1 一次。同理，边 0 − 12 只能交边 5 − 1 一次。此时，边 9 − 13 的两个端点处在不同的闭曲线中，由约当闭曲线定理得，边 9 − 13 交这两个闭曲线至少2次，此时 C r D ( Q 3 ) = 4 ，矛盾。

Figure 2. A good drawing of Q3

图2. Q3的画法D

Figure 3. A good drawing of M21

图3. 8圈M21的画法D1

情形2 8圈 M 21 自交1次。由于8圈 M 21 的8条边等价，不失一般性，选定边 0 − 1 作为产生交叉的一条边。剩下的边，根据与边 0 − 1 的距离分为3类，此时有3种子情形即 0 − 1 交 4 − 5 ， 0 − 1 交 5 − 9 ， 0 − 1 交 9 − 8 。

情形2.1 0 − 1 交 4 − 5 。如图4所示，若边 4 − 8 上不产生交叉，添入后，画法唯一，会分离3度点，矛盾。若边 4 − 8 上产生交叉，根据好的画法的定义，相邻边不能交，则 4 − 0 ， 4 − 5 ， 8 − 9 ， 8 − 12 不能交。若 4 − 8 交 1 − 13 ，画法唯一，分离3度点，因此 4 − 8 不能交 1 − 13 。记 0 − 1 交 4 − 5 的交叉点为x。同理，不能交 13 − 12 ， 5 − 9 ， 0 − x 。那么 4 − 8 只能交 0 − 1 ，同理， 0 − 12 只能交 4 − 5 。则在 Q 3 中，有两个边不相交的四圈 4 − 5 − 9 − 8 − 4 与 0 − 1 − 13 − 12 − 0 交3次，由约当闭曲线定理，两个边不相交的四圈产生偶数个交叉点，则至少交4次，矛盾。

Figure 4. Subdrawings of Q3

图4. Q3的子画法

情形2.2 0 − 1 交 5 − 9 。如图4所示，若边 0 − 12 上不产生交叉，添入后，画法唯一，会分离3度点，矛盾。若边 0 − 12 上产生交叉，根据好的画法的定义，相邻边不能交，则 4 − 0 ， 0 − 1 ， 12 − 8 ， 12 − 13 不能交。若 0 − 12 交 1 − 13 ，画法唯一，分离3度点，因此 0 − 12 不能交 1 − 13 。记 0 − 1 交 5 − 9 的交叉点为x。同理，不能交 9 − 8 ， 4 − 5 ， 5 − x 。那么 0 − 12 只能交 5 − 9 。添入 0 − 12 后，此时已有2个交叉。若边 4 − 8 上不产生交叉，添入后，画法唯一，会分离3度点，矛盾。若边 4 − 8 上产生交叉，根据好的画法的定义，相邻边不能交，则 4 − 0 ， 4 − 5 ， 8 − 9 ， 8 − 12 不能交。 4 − 8 的两个端点位于圈 0 − 1 − 13 − 12 − 0 的同一区域，添入 4 − 8 后，由约当闭曲线定理，与当前至少交2次，则在 Q 3 中，至少产生4个交叉，矛盾。

情形2.2 0 − 1 交 9 − 8 。如图4所示，若边 5 − 1 上不产生交叉，添入后，画法唯一，会分离3度点，矛盾。若边 5 − 1 上产生交叉，根据好的画法的定义，相邻边不能交，即 5 − 4 ， 5 − 9 ， 0 − 1 ， 1 − 13 不能交。若 5 − 1 交 4 − 0 ，画法唯一，分离3度点，因此 5 − 1 不能交 4 − 0 。记 0 − 1 交 9 − 8 的交叉点为x。同理，不能交 8 − 12 ， 12 − 13 ， 8 − x 。那么 5 − 1 只能交 9 − 8 ，同理， 9 − 13 只能交 0 − 1 。则在 Q 3 中，有两个边不相交的四圈 0 − 1 − 5 − 4 − 0 与 12 − 13 − 9 − 8 − 12 交3次，由约当闭曲线定理，两个边不相交的四圈产生偶数个交叉点，则至少交4次，矛盾。

情形3 8圈 M 21 自交2次。此时有2种子情形即一条边上产生两个交叉，四条边两两相交产生两个交叉。

情形3.1 一条边上产生两个交叉。由于8圈 M 21 的8条边等价，不失一般性，假设被交叉2次的边是 0 − 1 。设 n 1 为 0 − 1 与沿着8圈逆时针方向走，第一次被交叉的边之间的距离。 n 2 为被交叉1次的两条边之间的距离。由此得到10个不同的数组 ( n 1 , n 2 ) 即 ( 1 , 0 ) ， ( 1 , 1 ) ， ( 1 , 2 ) ， ( 1 , 3 ) ， ( 2 , 0 ) ， ( 2 , 1 ) ， ( 2 , 2 ) ， ( 3 , 0 ) ， ( 3 , 1 ) ， ( 4 , 0 ) 。其中不同的数组有着同构的画法即 ( 1 , 2 ) 与 ( 2 , 2 ) ， ( 2 , 0 ) 与 ( 3 , 0 ) ， ( 1 , 1 ) 与 ( 3 , 1 ) ， ( 1 , 0 ) 与 ( 4 , 0 ) 。

数组 ( 1 , 0 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 5 − 9 情形下，假设此时有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 4 − 8 至少有1条边干净。不失一般性，如果 4 − 8 干净，那么画法唯一，添入后，8个3度点分离，矛盾。

数组 ( 1 , 1 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 9 − 8 情形下，假设此时有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 5 − 1 ， 9 − 13 至少有2条边干净。不失一般性，如果交叉在 9 − 13 上，那么， 0 − 12 干净，那么画法唯一，添入后，8个3度点分离，矛盾。

数组 ( 1 , 2 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 8 − 12 情形下，假设此时有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 4 − 8 ， 5 − 1 ， 9 − 13 最多有1个交叉。不失一般性，如果交叉在 5 − 1 上，那么 4 − 8 ， 9 − 13 ， 0 − 12 干净，那么画法唯一，添入后，8个3度点分离，矛盾。数组 ( 1 , 3 ) ， ( 2 , 0 ) ， ( 2 , 1 ) 同理得到矛盾。

情形3.2 四条边两两相交产生两个交叉。由于8圈 M 21 的8条边等价，不失一般性，假设产生交叉的四条边中的任意一条是 0 − 1 。设 n 1 是产生第一组交叉的两条边之间的距离， n 2 是沿着8圈逆时针方向走，第一组交叉中的边与第二组交叉中的一条边之间的距离， n 3 是产生第二组交叉的两条边之间的距离。由此得到10个不同的数组 ( n 1 , n 2 , n 3 ) 即 ( 1 , 0 , 1 ) ， ( 1 , 0 , 2 ) ， ( 1 , 0 , 3 ) ， ( 1 , 1 , 1 ) ， ( 1 , 1 , 2 ) ， ( 1 , 2 , 1 ) ， ( 2 , 0 , 1 ) ， ( 2 , 0 , 2 ) ， ( 2 , 1 , 1 ) ， ( 3 , 0 , 1 ) 。其中不同的数组有着同构的画法即 ( 1 , 1 , 2 ) 与 ( 1 , 0 , 2 ) ， ( 1 , 2 , 1 ) 与 ( 1 , 0 , 1 ) ， ( 2 , 0 , 1 ) 与 ( 1 , 0 , 2 ) ， ( 2 , 1 , 1 ) 与 ( 1 , 1 , 2 ) ， ( 3 , 0 , 1 ) 与 ( 1 , 0 , 3 ) 。

数组 ( 1 , 0 , 1 ) 即 0 − 1 交 4 − 5 且 5 − 9 交 8 − 12 情形下，假设此时有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 4 − 8 ， 9 − 13 至少有2条边干净。不失一般性，如果交叉在 9 − 13 上，那么 4 − 8 ， 0 − 12 干净，那么画法唯一，添入后，8个3度点分离，矛盾。

数组 ( 1 , 0 , 2 ) 即 0 − 1 交 4 − 5 且 5 − 9 交 12 − 13 情形下，假设此时有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 4 − 8 至少有1条边干净。不失一般性，如果 4 − 8 干净，那么画法唯一，添入后，8个3度点分离，矛盾。数组 ( 1 , 0 , 3 ) ， ( 1 , 1 , 1 ) ， ( 2 , 0 , 2 ) 同理得到矛盾。

情形4 8圈 M 21 自交3次。此时有5种子情形即三条边两两相交，一条边上产生三个交叉，四条边产生三个交叉，五条边产生三个交叉，六条边两两产生三个交叉。

情形4.1 三条边两两相交产生三个交叉。由于相交的三条边互不相邻，8条边中相交的有3条，干净的有5条。任意一对相交的边间，至少有一条干净的边，那么这三条两两相交的边之间的距离的情况在等价意义下只有两种数组： ( 1 , 1 , 3 ) 与 ( 1 , 2 , 2 ) 。由于8圈 M 21 的8条边等价，不失一般性，假设 0 − 1 作为第一条边。

数组 ( 1 , 1 , 3 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 8 − 9 且 4 − 5 交 8 − 9 情形下，假设此时8圈 M 21 已有3个交叉点，且8个3度点在同一区域的边界上，那么 5 − 1 ， 9 − 13 ， 0 − 12 ， 4 − 8 全部干净，画法唯一，添入 0 − 12 后，8个3度点分离，矛盾。

数组 ( 1 , 2 , 2 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 8 − 12 且 4 − 5 交 8 − 12 情形下，假设此时8圈 M 21 已有3个交叉点，且8个3度点在同一区域的边界上，那么 9 − 13 ， 0 − 12 ， 4 − 8 全部干净，画法唯一，添入 0 − 12 后，8个3度点分离，矛盾。

情形4.2 一条边产生三个交叉。由于8圈 M 21 的8条边等价，不失一般性，假设被交叉3次的边是 0 − 1 。设 n 1 是 0 − 1 与沿着8圈逆时针方向走，第一次被交叉的边之间的距离， n 2 是沿着8圈逆时针方向走，第一次被交叉的边与第二次被交叉的边之间的距离， n 3 是沿着8圈逆时针方向走，第二次被交叉的边与第三次被交叉的边之间的距离。由此得到10个不同的数组 ( n 1 , n 2 , n 3 ) 即 ( 1 , 0 , 0 ) ， ( 1 , 0 , 1 ) ， ( 1 , 0 , 2 ) ， ( 1 , 1 , 0 ) ， ( 1 , 1 , 1 ) ， ( 1 , 2 , 0 ) ， ( 2 , 0 , 0 ) ， ( 2 , 0 , 1 ) ， ( 2 , 1 , 0 ) ， ( 3 , 0 , 0 ) 。其中不同的数组有着同构的画法即 ( 1 , 2 , 0 ) 与 ( 1 , 0 , 2 ) ， ( 2 , 0 , 1 ) 与 ( 1 , 1 , 0 ) ， ( 2 , 1 , 0 ) 与 ( 1 , 0 , 1 ) ， ( 3 , 0 , 0 ) 与 ( 1 , 0 , 0 ) 。

数组 ( 1 , 0 , 0 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 5 − 9 且 0 − 1 交 9 − 8 情形下，将这3个交叉固定在四圈 4 − 5 − 9 − 8 − 4 与四圈 0 − 1 − 13 − 12 − 0 时，可以得到两个边不相交的四圈已交3次，由引理1，则在 Q 3 中，至少产生4个交叉，矛盾。

数组 ( 1 , 0 , 2 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 5 − 9 且 0 − 1 交 12 − 13 情形下，在四圈 8 − 12 − 13 − 9 − 8 中已有一条边被交，由引理1，至少与四圈 0 − 1 − 4 − 5 − 0 交2次，此时还有一个交叉，但与已有的交叉不同，则在 Q 3 中，至少产生4个交叉，矛盾。数组 ( 1 , 0 , 1 ) 同理得到矛盾。

数组 ( 1 , 1 , 0 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 9 − 8 且 0 − 1 交 8 − 12 情形下，假设此时8圈 M 21 已有3个交叉点，且8个3度点在同一区域的边界上，那么 9 − 13 ， 0 − 12 ， 5 − 1 全部干净，画法唯一，添入 0 − 12 后，8个3度点分离，矛盾。

数组 ( 1 , 1 , 1 ) 即 0 − 1 交 4 − 5 且 0 − 1 交 9 − 8 且 0 − 1 交 12 − 13 情形下，假设此时8圈 M 21 已有3个交叉点，且8个3度点在同一区域的边界上，那么 0 − 12 ， 5 − 1 全部干净，画法唯一，添入 0 − 12 后，8个3度点分离，矛盾。

数组 ( 2 , 0 , 0 ) 即 0 − 1 交 5 − 9 且 0 − 1 交 9 − 8 且 0 − 1 交 8 − 12 情形下，假设此时8圈 M 21 已有3个交叉点，且8个3度点在同一区域的边界上，那么， 0 − 12 ， 5 − 1 ， 9 − 13 全部干净，画法唯一，添入 0 − 12 后，8个3度点分离，矛盾。

3. 结论

本文通过给出 C ( 16 , 4 ) 相应的好的画法，确定了其交叉数的上界。再利用反证法证明 c r ( C ( 16 , 4 ) ) ≥ 8 成立。假设 c r ( C ( 16 , 4 ) ) ≤ 7 ，则存在 C ( 16 , 4 ) 的好的画法D，使得 c r ( D ) ≤ 7 。我们记 G 1 的边集为 F 1 ， G 2 的边集为 F 2 ，F的边集为 F 12 。有 E ( C ( 16 , 4 ) ) = F 1 ∪ F 2 ∪ F 12 ，且 F 1 ∪ F 2 = F 1 ∪ F 12 = F 2 ∪ F 12 = Φ 。将好的画法D分为3个部分。结合公式及已有的定理引理，利用反证法证明循环图 C ( 16 , 4 ) 的交叉数为8。

文章引用

鲁东岳. 一类小阶图的交叉数
The Crossing Number of a Class of Small-Order Graphs[J]. 理论数学, 2023, 13(10): 3088-3094. https://doi.org/10.12677/PM.2023.1310319

参考文献

  1. 1. Turan, P.A. (1997) Note of Welcome. Journal of Graph Theory, 1, 7-9. https://doi.org/10.1002/jgt.3190010105

  2. 2. Garey, M.R. and Johnson, D.S. (1993) Crossing Number Is NP-Complete. SIAM Journal on Algebraic & Discrete Methods, 4, 312-316. https://doi.org/10.1137/0604033

  3. 3. Guy, R K. (1960) A Combinatorial Problem. Malayan Math. Soc., 7, 68-72.

  4. 4. Guy, R.K. (1969) Proof Techniques in Graph Theory. Academic Press, New York.

  5. 5. Kleitman, D.J. (1970) The Crossing Number of K5,n. Journal of Combinatorial Theory, 9, 315-325. https://doi.org/10.1016/S0021-9800(70)80087-4

  6. 6. Pan, S. and Richter, R.B. (2007) The Crossing Number of K11 Is 100. Journal of Graph Theory, 56, 128-134. https://doi.org/10.1002/jgt.20249

  7. 7. McQuillan, D., Pan, S.J. and Bruce Richter, R. (2015) On the Crossing Number of K13. Journal of Combinatorial Theory Series B, 115, 224-235. https://doi.org/10.1016/j.jctb.2015.06.002

  8. 8. Balogh, J., Lidicky, B. and Salazar, G. (2019) Closing in On Hill’s Conjecture. SIAM Journal on Discrete Mathematics, 33, 1261-1276. https://doi.org/10.1137/17M1158859

  9. 9. Fiorini, S. (1986) On the Crossing Number of Generalized Petersen Graphs. North-Holland Mathematics Studies, 123, 225-241. https://doi.org/10.1016/S0304-0208(08)73140-2

  10. 10. 郝荣霞, 刘彦佩. 关于循环图交叉数的新上界(英文) [J]. 运筹学学报, 1999(3): 1-6.

期刊菜单