【文章內容簡介】 去 S中的 |S|個結點，由歸納法易于證明 (見注 )： C\S的分圖個數不會超過所刪去的結點個數 |S|， 即w(C\S)?|S| 。 (2)次證 w(G\S)?w(C\S)： 由于 C\S是 G\S的一個生成子圖 ， 故此 G\S的邊要比 C\S的邊多 ， 因而 G\S的連通性要比 C\S的連通性強 ， 所以 G\S的分圖個數不會超過 C\S的分圖個數 ， 即 w(G\S) ? w(C\S) 。 最后 ， 根據 (1)和 (2)， 我們得到： w(G\S)?|S| 。 36 離散數學 注 ： ?[w(C\S)?|S| 的數學歸納法證明 ]. (1)[基始 ]當 |S|=1時 ， 在圈 C中刪去一個結點 ， 所得子圖 C\S是一條連通的路 ， 故有 w(C\S)=1?1=|S| ； (2)[歸納假設 ]當 |S|=k時 ， 假設有 w(C\S)?|S|=k； (3)[歸納 ]當 |S|=k+1時 ， 設 v是 S中的任一結點 ， 我們令 S?:=S\{v}，則有 |S?|=k。 于是根據歸納假設 有 w(C\S?)?|S?|； 而 S=S??{v}， 在圈 C上刪去 S的 k+1個 結點 ， 可分為兩步：先在 圈 C上刪去 S?的 k個 結點 ，將 圈 C分成 w(C\S?)段；然后在這些段的某一段上刪去結點 v； ① 若結點 v在該段的頭上 ， 則刪去結點 v， 不會增加分圖的個數 ， 即有 w(C\S)= w(C\S?)； ② 若結點 v不 在該段的頭上 (在中間 )，則刪去結點 v， 該段一分為二，分圖的個數會增加一，即有 w(C\S)= w(C\S?)+1； 于是，綜合 ① 和 ② 的結果，總有 w(C\S)?w(C\S?)+1?|S?|+1= |S| 。 ?定理 1實際上是將關于圖 G的討論轉化到其 H圈 C上的討論。這其實就是用了蹦圈法 。 37 離散數學 例 5(a)所示的圖 G不是 H圖。 在圖 5(a)中，有 9個結點。當將中間層上的三個結點刪去時 (即 S={v4, v5, v6}, |S| =3)， 此時圖 5(a)變?yōu)閳D 5(b)， 而圖 5(b) 的分圖個數為 4，即 w(G\S)=4?3= |S| ， 不滿足定理 1的必要性條件，故由定理 1知它不是 H圖。 圖 5 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 (b) v1 v2 v3 v7 v8 v9 38 離散數學 例 6(a)所示的 Petersen圖 P滿足定理 1的必要性條件，但卻不是 H圖。 Chvatalv在 1973 年用窮舉法證明了 P圖不是 H圖。 但 P圖滿足定理 1的必要性條件。這點可利用 P圖的軸對稱性，同樣用窮舉法來加以證明： 在 P圖中 ， 若刪去一個或兩個結點 ， 都不可能使原圖不連通； 若刪去三個結點 ， 最多只能得到具有兩個連通支的子圖 (一種情況如圖 6(b)所示 )； 若刪去四個結點 ， 最多只能得到具有三個連通支的子圖 (一種情況如圖 6(c)所示 ) ； 若刪去五個或五個以上的結點 ， 余下子圖的結點數都不超過 5， 故其連通支數必不會超過 5； 所以 Petersen圖滿足定理 1的必要性條件 。 39 離散數學 注 ： ?其余類似情況是對稱的 。 ?判定無向圖是 H圖的必要條件除了定理 1外 ， 還有兩個 ： 一個是標記法 (著色法 )。它是基于偶圖理論的，所以我們放在167。 ； 另一個是格林貝格－柯車列夫定理。它是基于平面圖理論的，所以我們放在 167。 。 ?判定 H圖 (H圈 )的充分性定理 (充分性條件 ) (b) (a) (c) 圖 6 P圖及其子圖 40 離散數學 定理 2.(D?K214。nig定理 (充分性定理 )) 設 G＝ (V, E)是簡單無向圖，且 |V|=n。則 對任意一對結點 u,v?V， 均有 deg(u)+deg(v)?n1 (*) ?G中必有一條 H路 。 [證 ].先證： G是連通的 (采用反證法 )； 假若不然 ， 則在圖 G中至少有兩個分圖 G1， G2(此間當然無邊相連 )。 設 G1有 n1個結點 ， G2有 n2個結點 。 任取結點 u0?G1， v0?G2。 注意到： n1+n2?n， deg(u0)?n11， deg(v0)?n21， 從而 deg(u0)+deg(v0) ?(n11)+ (n21)= n1+n2 2?n2?n1 這就與條件 (*)矛盾了 。 故圖 G是連通的 。 次證：圖 G中必有一條 H路； K246。nig算法 ： (用此算法必可求得圖 G中的一條 H路 ) 41 離散數學 G中任一結點 v出發(fā)，走出一條初級路，并將此路的兩端盡量延伸到盡頭。不妨設此路為 P=(v1, v2,?, vp) ， |P|=p1。 注：所謂將路的兩端已延伸到盡頭是指 ：?(?v0?V)((v0,v1)?E?(v0,v1)?P)??(?vp+1?V)((vP,vp+1)?E?(vp,vp+1)?P) 。 即路 P的兩個端點和不在路 P上的任何結點都不相鄰 。 若有相鄰 ，那么就立即向兩端延伸路 P ， 使它包含這些結點 。 也就是說 ： 這里得到的初級路 P， 它的兩端只與路中的某些結點相鄰 ， 而不與路 P之外的任何結點相鄰 。 p=n， 則此路 P已是 H路 。 exit ； 否則 p?n(故 p?n1)， 茲證明初級路 P必可被改造成一初級圈 C ， 且有 |C|= |P|+1 。 v1 v2 vp1 vp vp+1 v0 圖 P 42 離散數學 v1與端點 vp相鄰 ， 我們將邊 (v1,vp)并入路 P，則立即得到一初級圈 C= (v1, v2,?, vp , v1) ， 并且 |C|= |P|+1。 go to No5 。 v1與端點 vp不相鄰 ， 我們設與端點 v1相鄰的結點有 k個 ， 不妨設它們是 vi1, vi2,?, vik， 而且這些結點全都在路 P上 (否則 ， 路沒有走到盡頭 )。 這時 ， 端點 vp必至少與 k個結點 vi11, vi21,?, vik1中的某一個相鄰 (是指結點 vi1, vi2,?, vik在路 P上的前一個結點 )。 假若不然 ， 由于 deg(v1)=k ， 則 deg(vp)?p1k (與端點 vp相鄰的結點全都在路 P上 (否則 ， 路沒有走到盡頭 )。 路 P上共有 p個結點 ， 與結點vp相鄰的結點 ， 應該去掉結點 vp自己以及已設不于它相鄰的 k個 結點vi11, vi21,?, vik1 ， 不會超過 p1k個 結點 )。 于是 ， deg(v1)+deg(vp)?k+ (p1k)=p1?n1 (因 p?n) 這與條件 (*)矛盾 。 43 離散數學 從而不妨設結點 vp與結點 vij1(1?j?k)相鄰 ， 我們就立即得到一個通過結點 v1, v2,?, vp的初級圈： C= (v1, v2,?,vij1, vp , vp1 ,?,vij, v1) ,且 |C|= |P|1+2= |P|+1 (如圖 8所示 )。 注 ： 由 No3,No4可知 ： 不管 v1是 vp否與相鄰 ， 總可將 No1中得到的初級路變?yōu)槌跫壢?。 v2 v3 v1 圖 P改為初級圈Ｃ vp2 vp1 vp vij2 vij1 vij vij+1 vij+2 44 離散數學 ，茲證明初級圈 C必可被改造成一初級路 P (新 )，且有 |P|(新 ) = |C|= |P|(老 )+1 。 由于初級圈 C = (u1, u2,?, up , u1)(重新命名 ) 上只有 p個結點且 p?n， 故在圈 C外應該還有圖 G的結點。這些結點中必至少有一個 (不妨設是 w)與 C上的某個結點(不妨設是 uk (1?k?p))相鄰 (否則 ， 圖 G不連通 ) ，延伸 uk到 w， up up1 u2 u1 uk+1 uk w uk1 uk2 圖 P(新 ) 45 離散數學 并拆去 uk的一個鄰邊 (uk, uk+1)，這樣就得到了一條更長的初級路： P= (uk1, uk2,?,u1, u2 , up, up1,?,uk, w) ， 且 |P|(新 ) = |C|1+1= |C| = |P|(老 )+1 (如圖 9所示 )。 將 P的兩端延伸到盡頭， go to No2。 注 ： ?K246。nig算法一定會在有限步停止。因為算法每進入循環(huán)一次，初級路 P上結點的個數都會至少增一，而任何圖 G中結點的個數都是有限的； ?K246。nig算法的操作實際上是三步： (1)任走出一條初級路 P ，并延伸到盡頭； (2)改初級路 P為初級圈 C； (3)改初級圈 C為初級路 P (新 )，并延伸到盡頭；路長至少增 1。 ?容易看出 ， 定理 2中的條件 (*)對圖中是否存在著 H路是充分的而不是必要的。 46 離散數學 如圖 10中所示的六邊形圖 G， 雖然其任意兩個結點度數之和=45=61， 不滿足定理 2中的條件 (*)，但 G中顯然有 H路存在 (實際上 G是 H圖 ,有 H圈 )。 定理 3.(D?K214。nig定理 (充分性定理 )) 設 G＝ (V, E)是簡單無向圖，且 |V|=n。則 對任意一對結點 u,v?V， 均有 deg(u)+deg(v)?n (**) ?G必是 H圖。 圖 10 47 離散數學 [證 ].圖 G若滿足條件 (**)，則顯然滿足條件 (*)，故定理 2成立。因此圖 G中必存在著一條 H路 P， 不妨設： P=(v1, v2,?, vn) 。 現在我們來證圖 G中必含有 H圈： (1)若端點 v1與端點 vn相鄰 ， 我們將邊 (v1,vn)并入路 P，則立即得到一 H圈： C= (v1, v2,?, vn , v1) ； (2)若端點 v1與端點 vn不相鄰 ， 我們設與端點 v1相鄰的結點有 k個 ， 不妨設它們是 vi1, vi2,?, vik， 這些結點全都在路 P上 (因為路 P是 H路 ， 包含了圖 G中的所有結點 )。 這時 ， 端點 vn必至少與 k個結點 vi11, vi21,?, vik1中的某一個相鄰 (是指結點 vi1, vi2,?, vik在路 P上的前一個結點 )。 假若不然 ， 由于 deg(v1)=k ， 則 deg(vn)?n1k (與端點 vn相鄰的結點全都在路 P上 (因為路 P是 H路 )。 路 P上共有 n個結點 ， 與結點 vn相鄰 48 離散數學 的結點 ， 應該去掉結點 vn自己以及已設不于它相鄰的 k個 結點 vi11, vi21,?, vik1 ， 不會超過 n1k個 結點 )。 于是 ， deg(v1)+deg(vn)?k+ (n1k)=n1?n 這與條件 (**)矛盾 。 從而不妨設結點 vn與結點 vij1(1?j?k)相鄰 ， 我們就立即得到一 H圈： C= (v1, v2,?,vij1, vn , vn1 ,?,vij, v1) (如圖 11所示 )。 v2 v3 v1 圖 11 vn2 vn1 vn vij2 vij1 vij vij+1 vij+2 49 離散數學 根據 (1)和 (2)可知：圖 G中必含有一 H圈 ， 故圖 G必是H 圖 。 注 ： ?定理 3證明中的 (1)和 (2)實際上是 K246。nig算法的 No3和 No4步的翻版 ； ?K246。nig在 定理 3證明中的證明思想 ， 據傳來源于英國亞瑟王的謀士摩爾林 ， 在解決著名的 “ 圓桌會議 ” 座位排名方案時所用的方法：相傳亞瑟王有 2n名騎士 ， 每名騎士都有 n1名騎士是他的仇人 。 而大謀士摩爾林每當在亞瑟王召開 “ 圓桌會議 ” 時 ， 卻都能夠預先排定那張享有盛名的圓桌的座位名次