2、。規(guī)定κ’(不連通圖)=0，κ’(Kv)=υ-1。定義κ(G)>=k時(shí)，G叫做k連通圖；κ’(G)>=k時(shí)，G稱為k邊連通圖。k連通圖，當(dāng)k>1時(shí)，也是k-1連通圖。k邊連通圖，當(dāng)k>1時(shí)，也是k-1邊連通圖。上面就是頂連通與邊連通的概念，好象不指明的就是指頂連通了。?定理1κ(G)=<κ’(G)=<δ(可以復(fù)習(xí)一下第一章的1.2：δ=min{d(vi)})證：設(shè)d(v)=δ，則刪除與v邊關(guān)聯(lián)的δ條邊后，G變不連通圖，所以這δ條邊形成一個(gè)邊剖分集，故最小邊剖分集邊數(shù)不超過(guò)δ，即κ’(G)=<δ。下證κ=<κ’。分情形討論之。若G中無(wú)橋，
3、則有κ’>=2條邊，移去它們之后，G變成不連通圖。于是刪除這κ’條中的κ’-1條后，G變成有橋的圖。設(shè)此橋?yàn)閑=uv，我們對(duì)于上述κ’-1條刪去的每條邊上，選取一個(gè)端點(diǎn)，刪除這些(不超過(guò)κ’-1個(gè))端點(diǎn)，若G變得不邊能，則κ=<κ’-1；若仍連通，則再刪去u或v，即可使G變得不連通，于是κ=<κ’。證畢。這個(gè)定理很好理解，圖論中的一些定理常以這種“友好”的面目出現(xiàn)。?下面就是Whitmey定理?定理2(Whitney,1932)υ>=3的圖是2連通圖的充要條件是任二頂共圈(在一個(gè)圈上)。證：若任二頂共圈，任刪除一個(gè)頂w后，得圖G-w。任
4、取兩頂u,v∈V(G-w)，u,v在G中共存于圈C上，若w不在C上，則G-w中仍有圈C，即u與v在G-w中仍連通；若w在G中時(shí)在C上，在G-w中u與v在軌C-w上，故u與v仍連通。由u與v之任意性，G-w是連通圖，故κ(G)>=2，即G是2連通圖。反之，若G是2連通圖，υ>=3,任取u,v∈V(G)，用對(duì)d(u,v)的歸納法證明u與v之間有兩條無(wú)公共內(nèi)頂?shù)能壆?dāng)d(u,v)=1是時(shí)，因κ=<κ’=<δ，故κ’>=2，uv邊不是橋，G-uv仍連通，于是G-uv中存在從u到v的軌P1(u,v),這樣從u到v有兩條無(wú)公共內(nèi)頂?shù)能塒1(u,v)與
5、邊uv。假設(shè)d(u,v)=2),結(jié)論已成立，考慮d(u,v)=k的情形。令P0(u,v)之長(zhǎng)為k,w是P0(u,v)上與v相鄰的頂，則d(u,w)=k-1，由歸納法假設(shè)，在u,w之間有兩條無(wú)公共內(nèi)頂P與Q，因G是2連通較長(zhǎng)，故G-w仍連通。在G-w中存在軌P’(u,v)<>P0(u,v)，令x是P∪Q上P’的最后一個(gè)頂。因u∈P∪Q，故x存在(可能x=u)。不妨設(shè)x∈V(P)，則G有兩個(gè)u,v之間無(wú)公共內(nèi)頂?shù)能墸阂粋€(gè)是P上從u到x段并在P’上從x到v段；一個(gè)是Q+wv。證畢。?圖論的定理證明，沒(méi)有其他數(shù)學(xué)的那么多推導(dǎo)，那么多
6、的公式，符號(hào)也是有限的幾個(gè)，看多了就明白了。概念清晰還是很重要，很多東西是概念性的。還有就是構(gòu)造了，照題能構(gòu)造出的相應(yīng)的圖有時(shí)就迎而解了。就是打字時(shí)中英文切換麻煩。???????????3.2割頂、橋、塊?割頂、橋、塊都是一個(gè)圖的關(guān)鍵部位了。本節(jié)給出三個(gè)定理來(lái)闡述這三個(gè)概念，好象少了點(diǎn)，不過(guò)這本書的東西有些地方很語(yǔ)焉不詳?shù)模矣行〇|西到處穿插，并且有很強(qiáng)的理論性，很少涉及實(shí)踐中的問(wèn)題?？雌饋?lái)比較的累人。?定理3v是連通圖的一個(gè)頂點(diǎn)，則下可述命題等價(jià)：(1)??v是割頂(2)??存在與v不同的兩個(gè)頂u,w，使得v在每一條由u到w的軌上(
7、3)??存在V-{v}的一個(gè)劃分V-{v}=U∪W，U∩W=φ，使得對(duì)任意的u∈U,w∈W,v在每一條由u到w的軌上。??定理4x是G的一邊，G是連通圖，則下述命題等價(jià)：(1)???x是G的橋。(2)??????x不在G的任一圈上。(3)??????存在頂u,v∈V(G),使得x在每一個(gè)從u到v的軌上。(4)??????存在V(G)的劃分U與W，使得任二頂u,w,u∈U,w∈W時(shí)，x在每條從u到v的軌上。?上面的都沒(méi)什么可證的，就是軌、連通片、割頂、橋等概念翻來(lái)覆去的用就是了。?定理5G連通，υ>=3,則下列命題等價(jià)：(1)G是塊。(2
8、)??G的任二頂共圈。(3)??G的任一頂與任一邊共圈(4)??G的任二邊共圈(5)??任給G的二頂及一邊，存在連接此二頂含此邊之軌(6)??對(duì)G的三個(gè)不同的頂，存在一軌，連接其中兩個(gè)頂，含第三個(gè)頂(7)?
