线图与若干典型图类的交叉数研究

论文摘要

图的交叉数是近代图论中发展起来的一个重要概念,自从上个世纪五十年代初匈牙利数学家Paul Turán根据其在一个砖厂碰到的实际难题（Turán’s brick factory problem）,从而提出了交叉数的概念以来,图的交叉数逐渐成为国际上一个非常活跃的分支,使得很多图论专家对这方面进行了深入研究。 研究图的交叉数不仅具有重要理论意义,而且有较强的现实意义,如超大规模集成电路VLST中的圈布局问题、电子线路板设计中的布线问题等。1983年计算机科学家Carey和Johnson证明了确定图的交叉数是NP-完全问题,由于其难度,目前只知道一些特殊图类的交叉数,如完全图,完全2-部图,完全3-部图,圈与圈以及路与点数较少的图的笛卡尔积图,循环图,Petersen图以及线图等。关于非平面图,Kulli与Beineke等在1979年给出了使得它的线图的交叉数为1的条件;Jendrol′与Kle（?）于2001年研究了平面图的线图的交叉数为1的条件。关于完全2-部图Km,n,目前只能确定当m≤6时,Zarankiewicz猜想为真,而确定完全图Kn的交叉数目前也是一个公开问题。上世纪八十年代,Asano确定了完全3-部图K1,3,n和K2,3,n的交叉数。此后,关于完全3-部图一直没有新结果。 本文在第一章较为详细地介绍了目前图的交叉数研究的历史与现状,并简要介绍一些与本文有关的交叉数的概念。 在第二章,着重研究图及其线图的交叉数,给出了图与其线图的交叉数的有关性质,并得到了一个图与其线图的交叉数为都为k的充分必要条件: 设G为图,cr（G）=K（K≥1）,其线图为L（G）。若cr（L（G））=K,则当且仅当下列条件成立: （1） △（G）≤4,且G中每个4-度点都是割点; （2） 存在G的一个恰有K个交叉数的最优画法使得每条交叉的边关联G中的一个2度点。 该结果实质性地推广了Stanislav Jendrol′和Marian Kle（?）的关于非平面图和它的线图的交叉数都是1结果。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• §1.1 交叉数的历史背景与研究现状
• §1.2 一些基本概念
• 第二章 图与其线图的交叉数
• §2.1 引言
• §2.2 线图的特殊子图
• §2.3 图与其线图的交叉数的基本性质
• §2.4 定理2.1.4的必要性证明
• §2.5 定理2.1.4的充分性证明
• 1，4，n的交叉数'>第三章 完全3-部图K_1，4，n的交叉数
• §3.1 引言
• §3.2 定理3.1.3的证明
• 1，6，n、K_1，7，n及K_1，8，n的交叉数'>第四章 完全3-部图K_1，6，n、K_1，7，n及K_1，8，n的交叉数
• §4.1 引言
• 1，6，n的交叉数'>§4.2 完全3-部图K_1，6，n的交叉数
• 1，7，n和K_1，8，n的交叉数'>§4.3 完全3-部图K_1，7，n和K_1，8，n的交叉数
• 2，4，n的交叉数'>第五章 完全3-部图K_2，4，n的交叉数
• §5.1 引言
• §5.2 相关引理
• §5.3 定理5.1.1的证明
• 第六章 后记
• 参考文献
• 附录
• 攻读博士期间发表（接受发表）的学术论文
• 致谢
• 湖南师范大学学位论文原创性声明
• 湖南师范大学学位论文版权使用授权书