第五章圖論第二部分-資料下載頁(yè)
2025-07-20 21:20本頁(yè)面
【正文】 n階無(wú)向簡(jiǎn)單圖，若 G中任意不同的兩個(gè)頂點(diǎn)的度數(shù) 之和大于等于 n – 1，請(qǐng)證明 G是連通圖。 證明： 反證法。 假設(shè) G不連通。 不妨設(shè) G有 k個(gè)連通分支 G1， G2， …… ， Gk ， n1， n2， …… ， nk是各分支的頂點(diǎn)數(shù)。則有： n1 + n2 +…+n k = n 任取 u ? G1, v ? G2。 由 G是簡(jiǎn)單圖可知： deg(u) = n1 – 1 且 deg(v) = n2 – 1。 因此， deg(u) + deg(v) = n1 – 1 + n2 – 1 = n – 2 這與題設(shè)“任意不同的兩個(gè)頂點(diǎn)的度數(shù)之和大于等于 n – 1”矛盾。 ? G是連通圖 27 ? 設(shè)圖 G是無(wú)向簡(jiǎn)單圖。 請(qǐng)證明圖 G和補(bǔ)圖 ~G中至少有一個(gè)連通圖 。 證明： (1)如果 G是連通圖，問(wèn)題得證。 (2) 如果 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。 ∴ u和 v之間在 ~G中有通路 uxv相連。 由 u和 v的任意性，可知 ~G是連通的。 綜上所述， G和補(bǔ)圖 ~G中至少有一個(gè)是連通圖。 連通性證明舉例 4 28 課堂練習(xí) ? 證明：若 G是簡(jiǎn)單圖，設(shè) ?為 G的頂點(diǎn)的最小度，若 ??k，則 G中有長(zhǎng)為 k的基本通路。 29 課堂練習(xí)解答 ? 2. 證明： （反證法） 假設(shè) G中不存在長(zhǎng)度為 k的基本通路。 設(shè) P=v1v2… vm為 G中最長(zhǎng)基本通路。則 m?k。 假設(shè) vm與 V(G)V(P)中的一個(gè)結(jié)點(diǎn)相連，不妨設(shè)為 w，則 v1v2… vmw為比 P更長(zhǎng)的一條基本通路。這與P是 G中最長(zhǎng)的基本通路相矛盾。 因此， vm結(jié)點(diǎn)只能與 P上的結(jié)點(diǎn) v1,v2 , … ,vm1相連，故 d(vm)?m1?k1，進(jìn)而 ? ?d(vm)?k1，這與 ??k矛盾。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1