圖論及其應(yīng)用ppt(編輯修改稿)
2025-08-21 15:19 本頁面
【文章內(nèi)容簡(jiǎn)介】 明了定理 3。 例 7 設(shè) T為 12條邊的樹，其頂點(diǎn)度為 1,2,5。如果 T恰有3個(gè)度為 2的頂點(diǎn)，那么 T有多少片樹葉？ 解：設(shè) T有 x片樹葉。 由 m=n1得 n=13. 于是由握手定理得： 1 2 3 5 ( 1 0 ) 2 1 2xx? ? ? ? ? ? ? ? 1 0 x t 0 1 2 ?1 ? 0 1 n 13 得 x=8 例 8 設(shè) T為 (n, m)樹， T中有 ni個(gè)度為 i的點(diǎn) (1≦i≦k), 且有： ∑ ni=： 1 3 42 2 ( 2) kn n n k n? ? ? ? ? ?證明：由 m=n1得： 12( ) 1km n n n? ? ? ? ?又由握手定理得： 1222 km n n k n? ? ? ?由上面兩等式得： 1 3 42 2 ( 2) kn n n k n? ? ? ? ? ? 1 0 x t 0 1 2 ?1 ? 0 1 n 14 推論 1 具有 k個(gè)分支的森林有 nk條邊。 證明：設(shè)森林 G的 k個(gè)分支為 Ti (1≦i≦k). 對(duì)每個(gè)分支，使用定理 3得： ( ) 1 , ( ( ) )i i i im T n n V T? ? ?所以： 1( ) ( )k iim G m T n k?? ? ??定理 4 每個(gè) n階連通圖的邊數(shù)至少為 n1. 證明：如果 n階連通圖沒有一度頂點(diǎn)，那么由握手定理有： ()1( ) ( )2 v V Gm G d v n???? 1 0 x t 0 1 2 ?1 ? 0 1 n 15 如果 G有一度頂點(diǎn)。對(duì)頂點(diǎn)數(shù)作數(shù)學(xué)歸納。 當(dāng) n=1時(shí)，結(jié)論顯然 ()1( ) ( )2v V G um G u d v k??? ? ??設(shè)當(dāng) n=k時(shí)，結(jié)論成立。 當(dāng) n=k+1時(shí)，設(shè) u是 G的一度頂點(diǎn)，則 Gu為具有 k個(gè)頂點(diǎn)的連通圖。 若 Gu有一度頂點(diǎn)，則由歸納假設(shè)，其邊數(shù)至少 k1,于是 G的邊數(shù)至少有 k條； 若 Gu沒有一度頂點(diǎn)，則由握手定理： 所以 G至少有 k+1條邊。 1 0 x t 0 1 2 ?1 ? 0 1 n 16 而當(dāng) G是樹時(shí)，邊數(shù)恰為 n1. 所以 n階連通圖 G至少有 n1條邊。 所以，樹也被稱為最小連通圖。 定理 5 任意樹 T的兩個(gè)不鄰接頂點(diǎn)之間添加一條邊后，可以得到唯一圈。 證明：設(shè) u與 v是樹 T的任意兩個(gè)不鄰接頂點(diǎn)，由定理 2知：有唯一路 P連接 u與 P∪ ｛ u v｝是一個(gè)圈。 顯然，由 P的唯一性也就決定了 P∪ ｛ u v｝的唯一性。 例 9 設(shè) G是樹且 Δ≧ k,則 G至少有 k個(gè)一度頂點(diǎn)。 證明：若不然，設(shè) G有 n個(gè)頂點(diǎn)，至多 k1個(gè)一度頂點(diǎn)，由于 Δ≧ k，于是，由握手定理得：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1