第五章圖論第二部分(參考版)
2025-07-23 21:20本頁(yè)面
【正文】 因此， vm結(jié)點(diǎn)只能與 P上的結(jié)點(diǎn) v1,v2 , … ,vm1相連，故 d(vm)?m1?k1，進(jìn)而 ? ?d(vm)?k1，這與 ??k矛盾。 假設(shè) vm與 V(G)V(P)中的一個(gè)結(jié)點(diǎn)相連，不妨設(shè)為 w，則 v1v2… vmw為比 P更長(zhǎng)的一條基本通路。 設(shè) P=v1v2… vm為 G中最長(zhǎng)基本通路。 連通性證明舉例 4 28 課堂練習(xí) ? 證明：若 G是簡(jiǎn)單圖，設(shè) ?為 G的頂點(diǎn)的最小度，若 ??k，則 G中有長(zhǎng)為 k的基本通路。 由 u和 v的任意性，可知 ~G是連通的。 任取 u, v ? ~G，設(shè) G的連通分支有 G1， G2， …… ， Gk ① 如果 u和 v是屬于 G中不同的連通分支 Gi和 Gj，則 (u, v) ? ~G ② 如果 u和 v是屬于 G中相同的連通分支 Gi ，則可在 G的另一個(gè)連通分支中取一個(gè)結(jié)點(diǎn) x ，則 (u, x) ? ~G, (v, x) ? ~G。 證明： (1)如果 G是連通圖，問(wèn)題得證。 ? G是連通圖 27 ? 設(shè)圖 G是無(wú)向簡(jiǎn)單圖。 由 G是簡(jiǎn)單圖可知： deg(u) = n1 – 1 且 deg(v) = n2 – 1。 不妨設(shè) G有 k個(gè)連通分支 G1， G2， …… ， Gk ， n1， n2， …… ， nk是各分支的頂點(diǎn)數(shù)。 證明： 反證法。 因此， G是連通圖 。 則有： |V(G1)|?[|V(G)|/2]。 證明 ：（反證法） 假設(shè) G不是連通圖。 令 G’=Gv,則 G’有 k個(gè)頂點(diǎn)且 G’連通。 命題得證。 ? 1) 若 G中無(wú)度為 １ 的頂點(diǎn)，則 G中所有頂點(diǎn)的度數(shù)和 ≥2k＋２。 顯然 ,對(duì)所有 i=1,2,3,… ,m,都有 :xik. 由歸納假設(shè)可知 E(Gi)?xi1,而 v與每個(gè)連通分支至少有一條邊相連 ,故 E(Gi)?m+?i=1m(xi1)= m+?i=1mxim=?i=1mxi=k. 24 連通性證明題舉例 1(續(xù) ) (3) 證法二 : 顯然 , 在ｋ＋１個(gè)頂點(diǎn)中，不存在孤立頂點(diǎn)，否則，G不連通。 而由 v與 Gv至少有一條邊相連可知 : |E|?|E(Gv)|+1?ｋ 。 圖 G從 vi點(diǎn)到 vj點(diǎn)有通路當(dāng)且僅當(dāng)？ bij = 1 22 圖的連通性與可達(dá)矩陣 ? 有向圖的連通性（ n?1）：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1