圖的交叉數(shù)的研究已經(jīng)有幾十年的發(fā)展歷史,在這些年間,國內(nèi)外研究者取得了不少成果,但由于其探究的難度大,進(jìn)展十分緩慢。本文主要研究了一個(gè)小階循環(huán)圖交叉數(shù)的下界和一類循環(huán)圖的交叉數(shù)。主要內(nèi)容有:(1)證明循環(huán)圖C(13,5)交叉數(shù)的下界。通過去邊數(shù)的定義,首先可以確定C(13,5)的去邊數(shù)h≥5。而后采用反證法,將C(13,5)的邊集分成13個(gè)不同的4-圈,針對(duì)不同情況下刪掉去邊集中邊后得到的連通平面圖進(jìn)行討論。利用Euler公式等定理,得到所得平面圖的面的次數(shù)和與邊數(shù)的2倍不等的結(jié)果,因此假設(shè)不成立,確定C(13,5)交叉數(shù)的下界至少為6。(2)對(duì)于循環(huán)圖C(4k,4),由于可以確定一個(gè)交叉數(shù)為2k的好畫法,因此只需證明它的下界為2k即可。采用數(shù)學(xué)歸納法,以k=4時(shí),循環(huán)圖C(16,4)的交叉數(shù)是8為基礎(chǔ),假設(shè)k-1時(shí),不等式cr(C(4(k-1),4))≥2(k-1)成立。采用反證法,將C(4k,4)的邊集分成邊不相交的2k組,討論所有可能情況,證明cr(C(4k,4))≥2k。

【文章頁數(shù)】：41 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 交叉數(shù)的相關(guān)概念
    1.2 交叉數(shù)的發(fā)展
        1.2.1 完全圖
        1.2.2 完全二部圖
        1.2.3 完全三部圖
        1.2.4 廣義的Petersen圖
        1.2.5 循環(huán)圖
        1.2.6 笛卡爾積圖
    1.3 交叉數(shù)的應(yīng)用與現(xiàn)狀
2 循環(huán)圖C(13,5)交叉數(shù)的下界
    2.1 引言
    2.2 循環(huán)圖C(13,5)交叉數(shù)的下界
3 循環(huán)圖C(4k,4)交叉數(shù)的證明
    3.1 主要引理
    3.2 循環(huán)圖C(4k,4)的交叉數(shù)
結(jié)論
參考文獻(xiàn)
攻讀碩士學(xué)位期間發(fā)表學(xué)術(shù)論文情況
致謝



本文編號(hào)：3896113