半弧傳遞圖與整數(shù)流的研究.pdf

1、本文的主要內(nèi)容分為兩部分，前半部分是對4度半弧傳遞圖的研究，后半部分是對整數(shù)流的研究.這兩部分內(nèi)容都與群論有密切的關(guān)系.半弧傳遞圖與整數(shù)流理論這兩個研究課題同為國際著名數(shù)學家Tutte(英國皇家學會會員)所開創(chuàng). 第一章引言中我們系統(tǒng)地介紹了群與圖之間的聯(lián)系.詳細的描述了s-弧傳遞圖(尤其是半弧傳遞圖)的概念及研究進展.接下來我們對整數(shù)流的概念、問題的由來、著名的三大猜想以及一些已知的結(jié)論進行簡單的闡述. 半弧傳遞圖的研

2、究是由Tutte在1966年提出的，從此， 4度半弧傳遞圖的構(gòu)造和刻畫成為代數(shù)圖論的一個活躍分支. 4度半弧傳遞圖方面的內(nèi)容主要是借助群論的一些知識來構(gòu)造半弧傳遞圖并在某些條件下，給出4度半弧傳遞圖的分類.這一部分內(nèi)容主要集中在第二章至第四章. 第二章主要構(gòu)造了一類4度半弧傳遞圖.本章的主要內(nèi)容是把覆蓋的理論作為工具，研究K<,4.4>的正則覆蓋，并構(gòu)造出一類無限族的4度半弧傳遞圖.這類半弧傳遞圖的半徑為偶數(shù)且緊相關(guān)，它們不屬于

3、前人構(gòu)造的任何一類4度半弧傳遞圖. 第三章給出了當保纖維自同構(gòu)群包含一個半弧傳遞子群而且覆蓋變換群為素數(shù)冪階循環(huán)群時，K<,4.4>度半弧傳遞正則覆蓋的分類.通過這種分類，我們構(gòu)造了兩類無限族的4度半弧傳遞圖，它們是目前已知僅有的2冪階4度半傳遞圖無限類. 第四章給出了4p階4度半弧傳遞圖的分類，同時，我們還證明：4p階半弧傳遞圖一定不是Cayley圖. 后五章主要圍繞整數(shù)流理論，確切地說圍繞Tutte的3-流猜

4、想展開研究.Tutte3-流猜想已有五十多年歷史，至今沒有解決.本文考慮滿足某些條件的三大類圖，證明3-流猜想對這三類圖成立. 第五章給出了三角連通圖的3-流存在性以及 3-流可收縮性的完全刻畫.三角連通圖是任意兩條邊均有連續(xù)的三角形相連的一類圖.有了這個完全刻畫的結(jié)果，很多已知結(jié)果的證明都可以大大簡化. 第六章刻畫了在Ore-條件下3-流的存在性，除了六個特殊的圖外，其它的圖在Ore-條件下都能保證3-流的存在性.

5、 第七章則是應(yīng)用第五章的成果來研究度數(shù)和與3-流存在性以及 3-流可收縮性的關(guān)系，并且得到一個圖的每條邊的兩個端點度數(shù)和不小于頂點數(shù)時3-流存在的一個充要條件.當上面條件中的頂點數(shù)改為頂點數(shù)加2時這個條件則是保證 3-流可收縮性的一個充要條件(K<,4>除外). 第八章應(yīng)用同樣的方法研究最小度與3-流存在性的關(guān)系.事實上，從第七章的結(jié)論就可知如果一個圖的最小度不小于頂點數(shù)的一半時，除了個別圖外，都存在非零3-流.這里我們減弱