連通圖群連通性的度條件.pdf

1、本文考慮的圖均為有限圖,但是圖中可能包含重邊,對(duì)于圖G=G(V,E),我們用V(G)和E(G)表示圖的頂點(diǎn)集合與邊集合.對(duì)于圖G中的不相交頂點(diǎn)子集V1,V2,定義e(V1,V2)為端點(diǎn)分別在V1,V2中的邊的集合.特別的,當(dāng)V1=X,且V2=V(G)-X時(shí),用(δ)(X)代替e(X,V(G)-X).
　　 定義圖G上的方向D=D(G),若邊e∈E(G)的方向?yàn)橛牲c(diǎn)u到點(diǎn)v,則我們稱tail(e)=u與head(e)=v.并且對(duì)于

2、圖G中的一個(gè)頂點(diǎn)v∈V(G),定義
　　 E-D(v)={e∈E(D):v=tail(e)}與E+D(v)={e∈E(D):v=head(e)}.
　　 A是非平凡的阿貝爾加法群,0是它的加法單位元,記A*=A-0表示A中非零元素的集合,并定義函數(shù)
　　 F(G,A)={f:E(G)→A}與F*(G,A)={f:E(G)→A*}.
　　 給定函數(shù)f∈F(G,A),定義(δ)f:V(G)→A如下:
　

3、　 (δ)f(v)=∑e∈E+D(v)f(e)-∑e∈E-D(v)f(e)
　　 對(duì)于圖G,如果∑6(b)=0,則稱函數(shù)b:V(G)→A為A零值加和函數(shù).這種函數(shù)的集合用Z(G,A)表示.給定b∈Z(G,A),若存在函數(shù)f∈F*(G,A)使得(δ)f=b,則稱f為(A,b)-處處無零流.若對(duì)于任意b∈Z(G,A),圖G都存在(A,b)-處處無零流,則稱圖G為A連通的.
　　 作為解決圖的染色問題的重要工具,處處無零流理

4、論由Tutte在十九世紀(jì)五十年代提出.經(jīng)過半個(gè)世紀(jì)的研究與發(fā)展,其理論日益成熟和完善,并被推廣與擴(kuò)展到群連通理論.群連通理論作為處處無零流理論的延伸,不僅是解決一系列理論問題的重要方法與工具,同時(shí)在通信網(wǎng)絡(luò)設(shè)計(jì)、計(jì)算機(jī)科學(xué)等中都有非常重要的應(yīng)用.群連通理論研究的重心主要是在確定一般圖的群連通度上.
　　 本文主要討論了滿足一定度條件的一般圖的群連通度問題.全文共分三章,第一章簡(jiǎn)單介紹了圖論的基本概念,群連通理論的歷史與發(fā)展?fàn)顩r以

5、及一些已有的相關(guān)結(jié)論.
　　 第二章討論了滿足一定度條件的圖的群連通度,證明了以下結(jié)論:
　　 定理2.1.1 A為滿足|A|≥4的阿貝爾群,圖G為簡(jiǎn)單二邊連通圖,并且滿足n=|V(G)|≥21.如果對(duì)于任意u,v∈V(G)且uv(∈)E(G)都有maxd{d(u),d(v)}≥≥n/5,則圖GA-連通圖,或者G*∈圖集P.進(jìn)一步,若有G*∈{K2,5,K2,4,K2,3,C4},則有∧g(G)=5;若有G*=C5,則∧