有向圖中若干問題的研究.pdf

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

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

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