《樹的基本性質(zhì)》PPT課件.ppt

1、CH 3 樹,3.1 樹的基本性質(zhì),定義3.1.1 沒有回路的連通圖稱為樹，一般用 表示一棵樹。,例：左圖是兩棵有4個(gè)頂點(diǎn)的樹。 注: 只有一個(gè)頂點(diǎn)的樹就是K1,這一節(jié)我們介紹一類特殊的連通圖樹。,返回 結(jié)束,一、樹的特征 是樹，則若 ，就有 。事實(shí)上，由于 連通且 ，必有 。若 ，利用定理2.1.1， 中有回路，與 是樹矛盾。從而 是樹，若 ，就有 。 又由于 ，我們有,定理3.1.1 一個(gè)簡(jiǎn)單圖 是樹當(dāng)且僅當(dāng) 中任意兩個(gè)不同頂點(diǎn)之間有且只有一條路連接。,返回 結(jié)束,性質(zhì) 是樹 若 ，就有 ；,定理3.1.2 下述論斷是等價(jià)的： 1.圖 是樹（連通，無回路）； 2. 連通且 ； 3. 無回路

2、且 ； 4. 連通且 的每一條邊都是割邊； 5. 無回路且對(duì) 中任意兩個(gè)不相鄰的頂點(diǎn) ， 有且只有一個(gè)回路。,返回 結(jié)束,下面我們證1，2，3，4，5等價(jià)。證明方法 。,返回 結(jié)束,思考： 有什么性質(zhì)？,只要證明 無回路。采用反證法。設(shè) 中存在回路 。由習(xí)題2.14，有 仍連通。但 ， 與定理2.3.2矛盾。故 無回路。,先證明 連通。采用反證法 。 再證 的每條邊是割邊。,返回 結(jié)束,由于 的每條邊是割邊，所以 無回路，又因?yàn)?連通，故 是樹。設(shè) 和 是 中任意兩個(gè)不相鄰的頂點(diǎn)，由定理3.1.1知 中存在惟一的 路 則 就是 中唯一的回路。,證明 是樹。只要證明 是連通的。設(shè)非連通，在 的兩

3、個(gè)不同分支中各取一個(gè)頂點(diǎn) 和 ，明顯 仍無回路，與 滿足（5）矛盾,定理3.1.3 是樹且 ，則 至少有兩個(gè)懸掛點(diǎn)（度為1的點(diǎn)）。,證 設(shè) 是 的一個(gè)非懸掛點(diǎn)。 1。 2。 從而 不連通。即 是 的割點(diǎn)。,定義3.1.2 點(diǎn) 是 的割點(diǎn)，若 。,返回 結(jié)束,定理3.1.4 樹 的每個(gè)非懸掛點(diǎn)都是割點(diǎn)。,二、樹的中心點(diǎn),問題的提出：有下列若干居民區(qū)，居民 區(qū)間的距離如下圖所示，問醫(yī)院應(yīng)建在哪 個(gè)居民區(qū)才能使最遠(yuǎn)居民區(qū)的人到醫(yī)院看 病所走的路最短？,不難看出，一個(gè)圖 的直徑 為,定義3.1.3 圖 的一個(gè)頂點(diǎn) 的離徑 定義為,圖 的半徑 定義為,所有滿足 的頂點(diǎn) 都稱為 的中心。,定理3.1.5

4、設(shè) 是樹 的一條最長(zhǎng)路，則 （1） 的直徑為 ；（2）若 為奇數(shù)，設(shè) ，那么 的半徑為 ， 有兩個(gè)相鄰的中心，即為 和 。并且每一條長(zhǎng)為 的路都通過這兩個(gè)中心。（3）若 為偶數(shù),設(shè) ，那么 的半徑為 ，只有一個(gè)中心，即為 。并且每一條長(zhǎng)為 的路通過中心 。,證明： （1）由于樹 中只有唯一的一條 路 ，故 ，又因 是樹 的一條最 長(zhǎng)路，故 即為 的直徑。,（2）分二步進(jìn)行： 1。證明 ，有 ： 事實(shí)上， ，我們有,2。證明 和 ： 事實(shí)上，對(duì)每個(gè) ，若 ，明顯 的有 。 若 ；取 中一條 路 。 令 與 的第一個(gè)交點(diǎn)為 。記 由 的最長(zhǎng)性，有 和 。 下分 和 ，可以證明,3。證明任意一條長(zhǎng)為 的路一定通過 和,該定理說明了樹的中心點(diǎn)必定出現(xiàn)樹的最長(zhǎng)路上，且中心點(diǎn)只有1個(gè)或2個(gè),求