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