離散數(shù)學(xué)——樹-展示頁
2025-08-14 10:25本頁面
【正文】 設(shè) T是 n階非平凡的無向樹 ， 則 T中至少有兩片樹葉 。 只需證明 G是連通的。 又由于 G連通，所以 G為樹，由 (1) ?(2)可知， ?u,v∈ V， 且 u≠v， 則 u與 v之間存在唯一的路徑 Г， 則 Г∪ (u,v)（ (u,v)為加的新邊 ） 為 G中的圈， 顯然圈是唯一的。 (4)?(5) 如果 G是連通的且 G中任何邊均為橋 ，則 G中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈 。 只需證明 G中每條邊均為橋 。 1 1 1( 1 )s s si i ii i im m n n s n s? ? ?? ? ? ? ? ? ?? ? ?(3)?(4) 如果 G中無回路且 m＝ n1， 則 G是連通的且 m＝ n 1。 由 (1)?(2)?(3)可知 ， mi＝ ni1。 只需證明 G是連通的。 設(shè) n≤ k(k≥1) 時(shí)結(jié)論成立， 當(dāng) n=k+1時(shí)，設(shè) e＝ (u,v)為 G中的一條邊， 由于 G中無回路，所以 Ge為兩個(gè)連通分支 G G2。 其次證明 m＝ n1。 若 G中存在長度大于或等于 2的圈， 則圈上任何兩個(gè)頂點(diǎn)之間都存在兩條不同的路徑， 這也與已知矛盾。 首先證明 G中無回路。 若路徑不是唯一的，設(shè) Г1與 Г2都是 u到 v的路徑， 易知必存在由 Г1和 Г2上的邊構(gòu)成的回路， 這與 G中無回路矛盾。 由 G的連通性及定理 （ 在 n階圖 G中，若從頂點(diǎn) vi到vj(vi?vj)存在通路，則 vi到 vj 一定存在長度小于等于 n1的初級通路 (路徑 )）可知， ?u,v∈ V， u與 v之間存在路徑。 無向樹的等價(jià)定義 (1)?(2) 如果 G是樹 ，則 G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑 。 （ 5） G是連通的且 G中任何邊均為橋 。 （ 3） G中無回路且 m＝ n?1。 定理 設(shè) G＝ V,E是 n階 m條邊的無向圖 ， 則下面各命題是等價(jià)的： （ 1） G是樹 。 分支點(diǎn) —— 度數(shù) 大于或等于 2的頂點(diǎn)。 森林 —— 若無向圖 G至少有兩個(gè)連通分支（每個(gè)都是樹）。 無向樹及其性質(zhì) 定義 無向樹 —— 連通無回路的無向圖，簡稱樹，用 T表示。第 16章 樹 離 散 數(shù) 學(xué) 本章說明 ?樹是圖論中重要內(nèi)容之一。 ?本章所談 回路均指初級回路（圈）或簡單回路 ，不含復(fù)雜回路（有重復(fù)邊出現(xiàn)的回路）。 平凡樹 —— 平凡圖。 樹葉 —— 無向圖中懸掛頂點(diǎn)。 舉例 如圖為九個(gè)頂點(diǎn)的樹。 （ 2） G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑 。 （ 4） G是連通的且 m＝ n?1。 （ 6） G中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。 存在性。 唯一性 （反證法）。 (2)?(3) 如果 G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑 ， 則 G中無回路且 m＝ n1。 若 G中存在關(guān)聯(lián)某頂點(diǎn) v的環(huán)， 則 v到 v存在長為 0和 1的兩條路經(jīng) (注意初級回路是路徑的特殊情況 )， 這與已知矛盾。 (2)?(3) 如果 G中任意兩個(gè)頂點(diǎn)之間存在唯
外語相關(guān)推薦
鄂ICP備17016276號-1