哈工大集合論習(xí)題課-第六章 樹及割集 習(xí)題課(學(xué)生)

1、第六章 樹及割集習(xí)題課1課堂例題例1 設(shè)T是一棵樹，T有3個(gè)度為3頂點(diǎn)，1個(gè)2度頂點(diǎn)，其余均是1度頂點(diǎn)。則（1）求T有幾個(gè)1度頂點(diǎn)？（2）畫出滿足上述要求的不同構(gòu)的兩棵樹。分析：對(duì)于任一棵樹，其頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是：且，根據(jù)這些性質(zhì)容易求解。解：（1）設(shè)該樹的頂點(diǎn)數(shù)為，邊數(shù)為，并設(shè)樹中有個(gè)1度頂點(diǎn)。于是且，得。（2）滿足上述要求的兩棵不同構(gòu)的無(wú)向樹，如圖1所示。 圖1例2設(shè)G是一棵樹且，證明G中至少有k個(gè)度為1頂點(diǎn)。證：設(shè)中有個(gè)頂點(diǎn)，個(gè)樹葉，則中其余個(gè)頂點(diǎn)的度數(shù)均大于等于2，且至少有一個(gè)頂點(diǎn)的度大于等于。由握手定理可得：，有。所以中至少有個(gè)樹葉 。習(xí)題例1 若無(wú)向圖中有個(gè)頂點(diǎn)，條邊，則為樹。這

2、個(gè)命題正確嗎？為什么？解：不正確。與平凡圖構(gòu)成的非連通圖中有四個(gè)頂點(diǎn)三條邊，顯然它不是樹。例2設(shè)樹中有個(gè)度為1的頂點(diǎn)，有個(gè)度為2的頂點(diǎn)，有個(gè)度為3的頂點(diǎn)，則這棵樹有多少個(gè)頂點(diǎn)和多少條邊？解：設(shè)有個(gè)頂點(diǎn)，條邊，則。由有：，解得：=2。 故。例3證明恰有兩個(gè)頂點(diǎn)度數(shù)為1的樹必為一條通路。證：設(shè)是一棵具有兩個(gè)頂點(diǎn)度數(shù)為1的樹，則且。又除兩個(gè)頂點(diǎn)度數(shù)為1外，其他頂點(diǎn)度均大于等于2，故，即。因此個(gè)分支點(diǎn)的度數(shù)都恰為2，即為一條通路。例4 畫出具有4、5、6、7個(gè)頂點(diǎn)的所有非同構(gòu)的無(wú)向樹。解：4個(gè)頂點(diǎn)的非同構(gòu)的無(wú)向樹有兩棵，如圖2所示；5個(gè)頂點(diǎn)的非同構(gòu)的無(wú)向樹有3棵，如圖2所示。 （a） (b) (c)

3、(d) (e)圖26個(gè)頂點(diǎn)的非同構(gòu)的無(wú)向樹有6棵，如圖3所示。圖37個(gè)頂點(diǎn)的非同構(gòu)的無(wú)向樹有11棵，如圖4所示。所畫出的樹具有6條邊，因而七個(gè)頂點(diǎn)的度數(shù)之和應(yīng)為12。由于每個(gè)頂點(diǎn)的度數(shù)均大于等于1，因而可產(chǎn)生以下七種度數(shù)序列：（1）；（2）；（3）；（4）；（5）；（6）；（7）。在（1）中只有一個(gè)星形圖，因而只能產(chǎn)生1棵樹 。在（2），（3）中有兩個(gè)星形圖，因而也只能各產(chǎn)生1棵非同構(gòu)的樹，分別設(shè)為 。 在（4），（5）中有三個(gè)星形圖，但三個(gè)星形圖是各有兩個(gè)是同構(gòu)的，因而各可產(chǎn)生兩棵非同構(gòu)的樹，分別設(shè)為和。在（6）中，有四個(gè)星形圖，有三個(gè)是同構(gòu)的，考慮到不同的排列情況，共可產(chǎn)生三棵非同構(gòu)的樹，

4、設(shè)為。在（7）中，有五個(gè)星形圖，都是同構(gòu)的，因而可產(chǎn)生1棵樹，設(shè)為。七個(gè)頂點(diǎn)的所有非同構(gòu)的樹如圖2所示。 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11圖4例5設(shè)無(wú)向圖是由棵樹構(gòu)成的森林，至少在中添加多少條邊才能使成為一棵樹？解：設(shè)中的個(gè)連通分支為：，。在中添加邊，設(shè)所得新圖為，則連通且無(wú)回路，因而為樹。故所加邊的條數(shù)是使得為樹的最小數(shù)目。例6 證明：任意一棵非平凡樹都是偶圖。分析：若考慮一下數(shù)據(jù)結(jié)構(gòu)中樹（即有向樹）的定義，則可以很簡(jiǎn)單地將樹中的頂點(diǎn)按層次分類，偶數(shù)層頂點(diǎn)歸于頂點(diǎn)集，奇數(shù)層頂點(diǎn)歸于頂點(diǎn)集，圖中每條邊的端點(diǎn)一個(gè)屬于，另一個(gè)屬于，而不可能存在關(guān)聯(lián)同一個(gè)頂點(diǎn)集的

5、邊。同理，對(duì)于無(wú)向樹，可以從任何一個(gè)頂點(diǎn)出發(fā)，給該樹的頂點(diǎn)標(biāo)記奇偶性，例如，標(biāo)記，與相鄰的頂點(diǎn)標(biāo)記，再給與標(biāo)記為的所有相鄰的頂點(diǎn)標(biāo)記，依次類推，直到把所有的頂點(diǎn)標(biāo)記完為止。最后，根據(jù)樹的性質(zhì)證明，任何邊只可能關(guān)聯(lián)（標(biāo)記為 1的頂點(diǎn)集）和（標(biāo)記為0的頂點(diǎn)集）之間的頂點(diǎn)。證1從任何一個(gè)頂點(diǎn)出發(fā)，給該樹的頂點(diǎn)做標(biāo)記，標(biāo)記，與相鄰的頂點(diǎn)標(biāo)記，然后再給與標(biāo)記為的所有頂點(diǎn)相鄰的頂點(diǎn)標(biāo)記，依次類推，直到把所有的頂點(diǎn)標(biāo)記完為止。 下面證明：對(duì)于任何邊只能關(guān)聯(lián)（標(biāo)記為1的頂點(diǎn)集）和（標(biāo)記為0的頂點(diǎn)集）之間的頂點(diǎn)。不妨假設(shè)，若某條邊關(guān)聯(lián)中的兩個(gè)頂點(diǎn)，設(shè)為和，又因?yàn)楦鶕?jù)上述的標(biāo)記法則，有到的路和到的路。設(shè)與離和最近

6、的頂點(diǎn)為，所以，樹中存在回路：，與樹中無(wú)回路的性質(zhì)矛盾。所以，任意邊只能關(guān)聯(lián)（標(biāo)記為1的頂點(diǎn)集）和（標(biāo)記為0的頂點(diǎn)集）之間的頂點(diǎn)。所以，任意一棵非平凡樹都是偶圖。證2 設(shè)是任一棵非平凡樹，則無(wú)回路，即中所有回路長(zhǎng)都是零。而零是偶數(shù)，故由偶圖的判定定理可知是偶圖。例7（1）一棵無(wú)向樹有個(gè)度數(shù)為的頂點(diǎn)，。均為已知數(shù)，問應(yīng)為多少？（2）在（1）中，若未知，均為已知數(shù)，問應(yīng)為多少？解：（1）設(shè)為有個(gè)頂點(diǎn)，條邊無(wú)向樹，則，。由握手定理：，有，即 。 由式可知：。（2）對(duì)于，由可知： 。例8證明：任一非平凡樹最長(zhǎng)路的兩個(gè)端點(diǎn)都是樹葉。證：設(shè)為一棵非平凡的無(wú)向樹，為中最長(zhǎng)的路，若端點(diǎn)和中至少有一個(gè)不是樹葉，

7、不妨設(shè)不是樹葉，即有，則除與上的頂點(diǎn)相鄰?fù)猓卮嬖谂c相鄰，而不在上，否則將產(chǎn)生回路。于是仍為的一條比更長(zhǎng)的路，這與為最長(zhǎng)的路矛盾。故必為樹葉。 同理，也是樹葉。例9設(shè)無(wú)向圖中有個(gè)頂點(diǎn)，條邊，則為連通圖當(dāng)且僅當(dāng)中無(wú)回路。證：必要性：因?yàn)橹杏袀€(gè)頂點(diǎn)，邊數(shù)，又因?yàn)槭沁B通的，由定理可知為樹，因而中無(wú)回路。 充分性：因?yàn)橹袩o(wú)回路，又邊數(shù)，由定理可知為樹，所以是連通的。例10設(shè)是一個(gè)圖，證明：若，則中必有回路。證：（1）設(shè)是連通的，則若中無(wú)回路，則是樹，故與矛盾。故中必有回路。（2）設(shè)不連通，則中有個(gè)分支，。若中無(wú)回路，則的各個(gè)分支中也無(wú)回路，于是各個(gè)分支都是樹，所以有：，。相加得：與矛盾，故G中必有回路

8、。綜上所述，圖中必有回路。例11設(shè)是個(gè)正整數(shù)，且。證明存在一棵頂點(diǎn)度數(shù)為的樹。證：對(duì)頂點(diǎn)進(jìn)行歸納證明。當(dāng)時(shí)，則，故以為度數(shù)的樹存在，即為一條邊。設(shè)對(duì)任意個(gè)正整數(shù)，只要，則存在一棵頂點(diǎn)度數(shù)為的樹。對(duì)個(gè)正整數(shù)，若有，則中必有一個(gè)數(shù)為1，必有一個(gè)數(shù)大于等于2；不妨設(shè)，因此對(duì)個(gè)正整數(shù)，有，故存在一棵頂點(diǎn)度數(shù)為的樹。設(shè)中的度數(shù)為，在中增加一個(gè)頂點(diǎn)及邊，得到一個(gè)圖，則為樹。又的頂點(diǎn)度數(shù)為，故由歸納法知原命題成立。3.4 例題例1 的一條邊不包含在的任一回路中當(dāng)且僅當(dāng)是的橋。分析：這個(gè)題給出了判斷橋的充要條件，應(yīng)該記住。證：必要性：設(shè)是連通圖的橋，關(guān)聯(lián)的兩個(gè)頂點(diǎn)是和。若包含在的一個(gè)回路中，那么除邊外還有一條

9、分別以和為端點(diǎn)的路，所以刪去邊后，仍是連通的，這與是橋相矛盾。 充分性：若邊不包含在的任意回路中，則連接頂點(diǎn)和只有邊，而不會(huì)有其它連接和的路。因?yàn)槿暨B接和還有不同于邊的路，此路與邊就組成了一條包含邊的回路，從而導(dǎo)致矛盾。所以，刪去邊后，和就不連通了，故邊是橋。例2設(shè)是連通圖，滿足下面條件之一的邊應(yīng)具有什么性質(zhì) ？（1）在的任何生成樹中；（2）不在的任何生成樹中。解：（1）在的任何生成樹中的邊應(yīng)為中的橋。（2）不在的任何生成樹中的邊應(yīng)為中的環(huán)。例3 非平凡無(wú)向連通圖是樹當(dāng)且僅當(dāng)?shù)牡拿織l邊都是橋。證：必要性：若中存在邊不是橋，則仍連通，因而之間必另有一條（不通過）的路。設(shè)此路為：，于是中有回路，這與是樹矛盾，故的每條邊都是橋。 充分性：只要證明中無(wú)回路即可。若中有回路，則中任何邊都不是橋，與題設(shè)中每條邊都是橋矛盾。例4 圖1給出的帶權(quán)圖表示7個(gè)城市及架起城市間直接通信線路的預(yù)測(cè)造價(jià)，試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通信且總造價(jià)最小，要求計(jì)算出最小總造價(jià)。圖1 圖2 圖3解：該題就是求圖的最小生成樹問題。因此，圖的最小生成樹即為所求的通信線路圖，如圖2所示。其權(quán)即是最小總造價(jià)，其權(quán)為：。例7設(shè)是一棵