圖論是數(shù)學的一個分支,它以圖為研究對象,圖的頂點劃分問題一直都是圖論研究的熱點之一,在圖論研究中具有重要的理論意義,并且在計算機科學和信息科學等多個領域具有廣泛的應用.關于圖的頂點劃分問題已經(jīng)有了很多成果,最早的如著名的四色定理,即每個平面圖都會有一個(I,I,I,I)-劃分,這里的I代表的是獨立集.稀疏圖的(k,j)-劃分指的是將圖劃分成兩個部分,使得一個部分中的點的最大度小于等于k,另一個部分中的點的最大度小于等于j.一個圖當圍長大于等于5時會有一個(I,F)-劃分,這里F代表的是森林.一個圖G滿足最大平均度小于12/5時會有一個(I,F₁)-劃分,其中F₁指的是這個森林的每一個點的度數(shù)不超過1,等等.因此,找到合適的圖類并研究它的頂點劃分是非常有意義的.本論文主要研究稀疏圖的頂點劃分問題,總共分為四個章節(jié).第一章主要介紹了有關本論文的一些定義和術(shù)語,還有國內(nèi)外的有關頂點劃分的一些研究,以及本論文用到的主要方法.第二章證明了在滿足一定條件的圖類中,若一個圖的最大平均度至多是8/3,那么該圖有一個(I,O₃)-劃分,其...

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

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 基本符號和定義
    1.2 關于稀疏圖的頂點劃分問題的已有結(jié)果
        1.2.1 關于圖可以劃分成I和F的研究結(jié)果
        1.2.2 關于圖可以劃分成F和Δ_k的研究結(jié)果
        1.2.3 關于圖可以劃分成P_k和P_k的研究結(jié)果
        1.2.4 關于圖可以劃分成I和O_k的研究結(jié)果
        1.2.5 關于圖可以劃分成Δ_k和Δ_j的研究結(jié)果
    1.3 本文主要方法
第二章 稀疏圖的(I,O₃)-劃分
    2.1 圖類g₁的(I,O₃)-劃分
    2.2 極小反例的結(jié)構(gòu)特征
    2.3 權(quán)轉(zhuǎn)移過程
第三章 稀疏圖的(I,O₄)-劃分
    3.1 圖類g₂的(I,O₄)-劃分
    3.2 極小反例的結(jié)構(gòu)特征
    3.3 權(quán)轉(zhuǎn)移過程
第四章 總結(jié)與展望
參考文獻
致謝



本文編號：3803156