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