(無(wú)向)樹(shù)沒(méi)有回路的連通圖

第六章樹(shù)（無(wú)向）樹(shù)：沒(méi)有回路的連通圖根樹(shù)是計(jì)算機(jī)科學(xué)最常用的概念之一根樹(shù)以（無(wú)向）樹(shù)為基礎(chǔ)6.1樹(shù)定義1（無(wú)向）樹(shù)：無(wú)簡(jiǎn)單回路的連通圖 樹(shù)葉：樹(shù)中度為1的頂點(diǎn) 森林：無(wú)簡(jiǎn)單回路的圖（多棵樹(shù)）樹(shù)必定不是多重圖、偽圖森林的每個(gè)連通分支都是樹(shù)例

定理1

無(wú)向圖是樹(shù)每對(duì)頂點(diǎn)之間存在唯一的基本通路

證明：首先假定T是樹(shù)。則T是沒(méi)有簡(jiǎn)單回路的連通圖。設(shè)x和y是T的兩個(gè)頂點(diǎn)。因?yàn)門是連通的，根據(jù)連通性定理1，在x和y之間存在一條簡(jiǎn)單通路。另外，這兩條通路必然是唯一的，因?yàn)榧偃绱嬖诘诙l這樣的通路，則組合從x到y(tǒng)的第一條這樣的通路以及經(jīng)過(guò)倒轉(zhuǎn)從x到y(tǒng)的第二條通路的順序所得到的從y到x的通路，就形成了回路。利用5.4節(jié)習(xí)題5，這蘊(yùn)含著在T中存在簡(jiǎn)單回路。因此，在樹(shù)的任何兩個(gè)頂點(diǎn)之間存在唯一簡(jiǎn)單通路。 現(xiàn)在假定在圖T的任何兩個(gè)點(diǎn)頂點(diǎn)之間存在唯一簡(jiǎn)單通路。則T是連通的，因?yàn)樵谒娜魏蝺蓚€(gè)頂點(diǎn)之間存在通路。另外，T沒(méi)有簡(jiǎn)單回路。為了看出這句話是真的，假定T有包含頂點(diǎn)x和y的簡(jiǎn)單回路。則在x和y之間就有兩條簡(jiǎn)單通路，因?yàn)檫@條簡(jiǎn)單回路包含一條從x到y(tǒng)的簡(jiǎn)單通路和一條從y到x的簡(jiǎn)單通路。因此，在任何兩個(gè)頂點(diǎn)之間存在唯一簡(jiǎn)單通路的圖是樹(shù)。定理2n階無(wú)向圖是樹(shù)無(wú)向圖連通，且n-1有條邊 證明： 用數(shù)學(xué)歸納法。在歸納步驟中，刪除1邊，成為兩棵樹(shù)。 用反證法。若非樹(shù)，則有回路，去掉回路中的1條邊仍然保持連通性。如此重復(fù)，直到成為樹(shù)，有n-1>X=n-1條邊，與條件矛盾例

1一棵樹(shù)有2個(gè)4度頂點(diǎn)，3個(gè)3度頂點(diǎn)，其余都是樹(shù)葉，問(wèn)該樹(shù)有幾片樹(shù)葉？ 解：設(shè)該樹(shù)有n1片樹(shù)葉，有m條邊，n個(gè)頂點(diǎn) 根據(jù)樹(shù)的性質(zhì) 由握手定理得

該樹(shù)有9片樹(shù)葉。定理樹(shù)中任意加一條邊就形成回路

證明：若在連通圖G中兩個(gè)不相鄰的結(jié)點(diǎn)vi和vj之間添加一條邊{vi,vj}，因?yàn)镚中原來(lái)存在vi到vj的通路，故此時(shí)形成一條經(jīng)過(guò)vi和vj的回路。習(xí)題 證明：簡(jiǎn)單圖是樹(shù)，當(dāng)且僅當(dāng)它是連通的，但是刪除它的任何一條邊就產(chǎn)生不連通的圖。6.2根樹(shù)定義有向樹(shù)：有向圖，底圖是有向樹(shù) 根樹(shù)：有一個(gè)頂點(diǎn)（稱為根）的入度為0，其余頂點(diǎn)的入度均為1例定理根樹(shù)中，從根到其余每個(gè)頂點(diǎn)有且僅有一條通路 證明：因?yàn)門是根樹(shù)，則作為無(wú)向圖而言，根結(jié)點(diǎn)到任何結(jié)點(diǎn)均有通路，若無(wú)有向通路，則一定存在某個(gè)結(jié)點(diǎn)，其