PAGE9哈工大集合論習題課-第六章樹及割集習題課(學生)第六章樹及割集習題課1課堂例題例1設T是一棵樹，T有3個度為3頂點，1個2度頂點，其余均是1度頂點。則（1）求T有幾個1度頂點？（2）畫出滿足上述要求的不同構的兩棵樹。分析：對于任一棵樹，其頂點數和邊數的關系是：且，根據這些性質容易求解。解：（1）設該樹的頂點數為，邊數為，并設樹中有個1度頂點。于是且，，得。（2）滿足上述要求的兩棵不同構的無向樹，如圖1所示。圖1例2設G是一棵樹且，證明G中至少有k個度為1頂點。證：設中有個頂點，個樹葉，則中其余個頂點的度數均大于等于2，且至少有一個頂點的度大于等于。由握手定理可得：，有。所以中至少有個樹葉。習題例1若無向圖中有個頂點，條邊，則為樹。這個命題正確嗎？為什么？解：不正確。與平凡圖構成的非連通圖中有四個頂點三條邊，顯然它不是樹。例2設樹中有個度為1的頂點，有個度為2的頂點，有個度為3的頂點，則這棵樹有多少個頂點和多少條邊？解：設有個頂點，條邊，則。由有：，解得：=2。故。例3證明恰有兩個頂點度數為1的樹必為一條通路。證：設是一棵具有兩個頂點度數為1的樹，則且。又除兩個頂點度數為1外，其他頂點度均大于等于2，故，即。因此個分支點的度數都恰為2，即為一條通路。例4畫出具有4、5、6、7個頂點的所有非同構的無向樹。解：4個頂點的非同構的無向樹有兩棵，如圖2所示；5個頂點的非同構的無向樹有3棵，如圖2所示。（a）(b)(c)(d)(e)圖26個頂點的非同構的無向樹有6棵，如圖3所示。圖37個頂點的非同構的無向樹有11棵，如圖4所示。所畫出的樹具有6條邊，因而七個頂點的度數之和應為12。由于每個頂點的度數均大于等于1，因而可產生以下七種度數序列：（1）；（2）；（3）；（4）；（5）；（6）；（7）。在（1）中只有一個星形圖，因而只能產生1棵樹。在（2），（3）中有兩個星形圖，因而也只能各產生1棵非同構的樹，分別設為。在（4），（5）中有三個星形圖，但三個星形圖是各有兩個是同構的，因而各可產生兩棵非同構的樹，分別設為和。在（6）中，有四個星形圖，有三個是同構的，考慮到不同的排列情況，共可產生三棵非同構的樹，設為。在（7）中，有五個星形圖，都是同構的，因而可產生1棵樹，設為。七個頂點的所有非同構的樹如圖2所示。T1T2T3T4T5T6T7T8T9T10T11圖4例5設無向圖是由棵樹構成的森林，至少在中添加多少條邊才能使成為一棵樹？解：設中的個連通分支為：，，。在中添加邊，，設所得新圖為，則連通且無回路，因而為樹。故所加邊的條數是使得為樹的最小數目。例6證明：任意一棵非平凡樹都是偶圖。分析：若考慮一下數據結構中樹（即有向樹）的定義，則可以很簡單地將樹中的頂點按層次分類，偶數層頂點歸于頂點集，奇數層頂點歸于頂點集，圖中每條邊的端點一個屬于，另一個屬于，而不可能存在關聯同一個頂點集的邊。同理，對于無向樹，可以從任何一個頂點出發，給該樹的頂點標記奇偶性，例如，標記，與相鄰的頂點標記，再給與標記為的所有相鄰的頂點標記，依次類推，直到把所有的頂點標記完為止。最后，根據樹的性質證明，任何邊只可能關聯（標記為1的頂點集）和（標記為0的頂點集）之間的頂點。證1從任何一個頂點出發，給該樹的頂點做標記，標記，與相鄰的頂點標記，然后再給與標記為的所有頂點相鄰的頂點標記，……，依次類推，直到把所有的頂點標記完為止。下面證明：對于任何邊只能關聯（標記為1的頂點集）和（標記為0的頂點集）之間的頂點。不妨假設，若某條邊關聯中的兩個頂點，設為和，又因為根據上述的標記法則，有到的路和到的路。設與離和最近的頂點為，所以，樹中存在回路：，與樹中無回路的性質矛盾。所以，任意邊只能關聯（標記為1的頂點集）和（標記為0的頂點集）之間的頂點。所以，任意一棵非平凡樹都是偶圖。證2設是任一棵非平凡樹，則無回路，即中所有回路長都是零。而零是偶數，故由偶圖的判定定理可知是偶圖。例7（1）一棵無向樹有個度數為的頂點，。均為已知數，問應為多少？（2）在（1）中，若未知，均為已知數，問應為多少？解：（1）設為有個頂點，條邊無向樹，則，。由握手定理：，有，即。①由式①可知：。（2）對于，由①可知：。例8證明：任一非平凡樹最長路的兩個端點都是樹葉。證：設為一棵非平凡的無向樹，為中最長的路，若端點和中至少有一個不是樹葉，不妨設不是樹葉，即有，則除與上的頂點相鄰外，必存在與相鄰，而不在上，否則將產生回路。于是仍為的一條比更長的路，這與為最長的路矛盾。故必為樹葉。同理，也是樹葉。例9設無向圖中有個頂點，條邊，則為連通圖當且僅當中無回路。證：必要性：因為中有個頂點，邊數，又因為是連通的，由定理可知為樹，因而中無回路。充分性：因為中無回路，又邊數，由定理可知為樹，所以是連通的。例10設是一個圖，證明：若，則中必有回路。證：（1）設是連通的，則若中無回路，則是樹，故與矛盾。故中必有回路。（2）設不連通，則中有個分支，。若中無回路，則的各個分支中也無回路，于是各個分支都是樹，所以有：，。相加得：與矛盾，故G中必有回路。綜上所述，圖中必有回路。例11設是個正整數，，且。證明存在一棵頂點度數為的樹。證：對頂點進行歸納證明。當時，，則，故以為度數的樹存在，即為一條邊。設對任意個正整數，只要，則存在一棵頂點度數為的樹。對個正整數，若有，則中必有一個數為1，必有一個數大于等于2；不妨設，因此對個正整數，有，故存在一棵頂點度數為的樹。設中的度數為，在中增加一個頂點及邊，得到一個圖，則為樹。又的頂點度數為，故由歸納法知原命題成立。3.4例題例1的一條邊不包含在的任一回路中當且僅當是的橋。分析：這個題給出了判斷橋的充要條件，應該記住。證：必要性：設是連通圖的橋，關聯的兩個頂點是和。若包含在的一個回路中，那么除邊外還有一條分別以和為端點的路，所以刪去邊后，仍是連通的，這與是橋相矛盾。充分性：若邊不包含在的任意回路中，則連接頂點和只有邊，而不會有其它連接和的路。因為若連接和還有不同于邊的路，此路與邊就組成了一條包含邊的回路，從而導致矛盾。所以，刪去邊后，和就不連通了，故邊是橋。例2設是連通圖，滿足下面條件之一的邊應具有什么性質？（1）在的任何生成樹中；（2）不在的任何生成樹中。解：（1）在的任何生成樹中的邊應為中的橋。（2）不在的任何生成樹中的邊應為中的環。例3非平凡無向連通圖是樹當且僅當的的每條邊都是橋。證：必要性：若中存在邊不是橋，則仍連通，因而之間必另有一條（不通過）的路。設此路為：，于是中有回路，這與是樹矛盾，故的每條邊都是橋。充分性：只要證明中無回路即可。若中有回路，則中任何邊都不是橋，與題設中每條邊都是橋矛盾。例4圖1給出的帶權圖表示7個城市及架起城市間直接通信線路的預測造價，試給出一個設計方案使得各城市間能夠通信且總造價最小，要求計算出最小總造價。圖1圖2圖3解：該題就是求圖的最小生成樹問題。因此，圖的最小生成樹即為所求的通信線路圖，如圖2所