一类循环图的交叉数

发布时间：2024-02-05 19:52

　　图的交叉数的研究已经有几十年的发展历史,在这些年间,国内外研究者取得了不少成果,但由于其探究的难度大,进展十分缓慢。本文主要研究了一个小阶循环图交叉数的下界和一类循环图的交叉数。主要内容有:(1)证明循环图C(13,5)交叉数的下界。通过去边数的定义,首先可以确定C(13,5)的去边数h≥5。而后采用反证法,将C(13,5)的边集分成13个不同的4-圈,针对不同情况下删掉去边集中边后得到的连通平面图进行讨论。利用Euler公式等定理,得到所得平面图的面的次数和与边数的2倍不等的结果,因此假设不成立,确定C(13,5)交叉数的下界至少为6。(2)对于循环图C(4k,4),由于可以确定一个交叉数为2k的好画法,因此只需证明它的下界为2k即可。采用数学归纳法,以k=4时,循环图C(16,4)的交叉数是8为基础,假设k-1时,不等式cr(C(4(k-1),4))≥2(k-1)成立。采用反证法,将C(4k,4)的边集分成边不相交的2k组,讨论所有可能情况,证明cr(C(4k,4))≥2k。

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 交叉数的相关概念
    1.2 交叉数的发展
        1.2.1 完全图
        1.2.2 完全二部图
        1.2.3 完全三部图
        1.2.4 广义的Petersen图
        1.2.5 循环图
        1.2.6 笛卡尔积图
    1.3 交叉数的应用与现状
2 循环图C(13,5)交叉数的下界
    2.1 引言
    2.2 循环图C(13,5)交叉数的下界
3 循环图C(4k,4)交叉数的证明
    3.1 主要引理
    3.2 循环图C(4k,4)的交叉数
结论
参考文献
攻读硕士学位期间发表学术论文情况
致谢



本文编号：3896113