有向圖中若干問(wèn)題的研究.pdf

1、該篇論文主要研究有向圖中的有向圈,討論有向圖中的圍長(zhǎng)g(D)(最短有向圈的長(zhǎng)度)與圖的頂點(diǎn)度以及結(jié)合數(shù)之間的關(guān)系,并重點(diǎn)分析了點(diǎn)可遷圖類.論文源自于有向圖中兩個(gè)具有一定相關(guān)性的猜想:在論文的第一章,我們介紹了論文中涉及的一些基本的圖論概念和術(shù)語(yǔ),該論文的研究?jī)?nèi)容以及論文中所得到的主要結(jié)果.第二章綜述了上述兩個(gè)猜想的研究進(jìn)展.重點(diǎn)介紹了Caccetta-Haggkvist猜想的特殊情形:給出了與Caccetta-Haggkvist猜想或其

2、特殊情形等價(jià)的相關(guān)猜想.證明了Seymour二出度猜想成立等價(jià)于該猜想在強(qiáng)連通有向圖上成立.第三章討論理論和應(yīng)用上都非常重要的特殊圖類——可遷圖.我們將許多無(wú)向點(diǎn)可遷圖的結(jié)果平行地推廣到有向點(diǎn)可遷圖中,同時(shí)得到了一些不同與無(wú)向圖情形的結(jié)論.證明了Caccetta-Haggkvist猜想和Seymour二出度猜想均在可遷圖上成立.重點(diǎn)討論了點(diǎn)可遷圖的連通性及連通度,提出了原子匹配、原子收縮圖、原子穩(wěn)定子群等一些新的概念,第四章將有向圖的度

3、條件(頂點(diǎn)的鄰域)與圍長(zhǎng)的關(guān)系進(jìn)行了推廣,考慮結(jié)合數(shù)(點(diǎn)集合的鄰域條件)與圍長(zhǎng)的關(guān)系.由于若無(wú)向圖G的結(jié)合數(shù)b(G)≥3/2,則G中存在三角形,而Caccetta-Haggkvist猜想研究有向圖中存在有向三角形的條件,受此啟發(fā),我們?cè)谟悬c(diǎn)向圖中引入結(jié)合數(shù)的概念.在此基礎(chǔ)上,論文討論了有向圖結(jié)合數(shù)的性質(zhì),得到了結(jié)合數(shù)的范圍并論證了給定結(jié)合數(shù)的有向圖的存在性,提出了關(guān)于結(jié)合數(shù)與圍長(zhǎng)之間聯(lián)系的兩個(gè)猜想.最后,我們對(duì)該論文的結(jié)果加以總結(jié),歸納