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

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

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

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

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

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

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

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

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

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