1、設(shè)一個樹中度為k的結(jié)點數(shù)是nk(2k)，求它的葉的數(shù)目。 解：設(shè)n個結(jié)點的樹有t個葉， 由已知n=t+ni 2(n-1)=t+ ini 消去式中的n: 2= t+ (2-i)ni 即： t= (i-2)ni + 2,i=2,i=2,i=2,i=3,習題十一 1,設(shè)e是連通圖的一條邊，證明: e是割邊當且僅當e含于G的每個生成樹中. 證明: ()如果割邊e不在G的某個生成樹中,則G- e仍有生成樹,即仍連通,與割邊的定義相矛盾. ()如果e是每個生成樹的公共邊,則去掉e后G- e不再連通,即e為G 的割邊.,習題十一 10,樹T中最長道路的起點和終點必都是T的葉. 證明: 設(shè)u到v的道路是樹中最

2、長道路，如果u或v不是葉，由道路唯一性，必有u或v的鄰接結(jié)點不在該道路上，因此這條道路可延長至w，與最長條件矛盾。,習題十一 2,用Kruskal算法求圖的一個最小生成樹。 解：邊按序排列：ab,gc,eg,ed,af,fd,fe,dc,fb,bd,ag,bc 按算法構(gòu)造生成樹邊集為：ab,gc,eg,ed,af,fd, W(T)=8.,a,g,f,e,d,c,b,1,3,2,1,3,2,1,1,4,4,6,5,習題十一 12,用Kruskal定理證明Peterson圖不是平面圖。 證明：下面是Peterson圖的一個子圖， 它與k3,3的細分圖同構(gòu)，所以Peterson圖不是平面圖。,設(shè)G是

3、階數(shù)不小于11的圖，證明：G或G中至少有一個是非平面圖。 證明：假設(shè)G和G都是平面圖，可得n(n-1)/2 6n-12， 所以 n2-13n+24 0 可得n10，與已知矛盾。所以原題得證。,習題十二 3,證明：少于30條邊的簡單平面圖至少有一個頂點的度不大于4。 證明：假設(shè) 5，可得 5n 2m 由平面性，2m 6n-12 再將n 12 代入5n 2m ，得m 30，與已知矛盾。所以原題得證。, n 12,習題十二 5,若一平面圖與其對偶圖同構(gòu)，則稱這個平面圖為自對偶圖。推導自對偶圖必須滿足的結(jié)點數(shù)n與邊數(shù)m的關(guān)系，并找出一個自對偶圖。 解：如果G是自對偶圖，在歐拉公式中必有n=f, 于是m

4、=2(n-1).,習題十二 9,設(shè)G=（V，E）是一個具有2k(k0)個奇數(shù)度結(jié)點的連通圖。證明：G中必存在k條邊不相重的簡單道路P1,P2,Pk, 使得E=E(P1) E(P2) E(Pk). 證明：把2k個奇數(shù)度結(jié)點分成兩兩一組的k組，然后每組結(jié)點新加一條邊，所得圖為歐拉圖，故存在歐拉回路。 再去掉歐拉回路中的k條新加入的邊，得到k條互無重復邊的道路P1,P2,Pk, 即為所求。,習題十三 2,v9,v6,v3,v1,求圖中，中國郵遞員問題的解。 解：圖中有4個奇數(shù)度結(jié)點v1,v6,v9,v3, 求兩兩之間最短長度： Pv1v6=3 (v1v6), Pv1v9=7 (v1v2v3v4v9)

5、, Pv1v3=4 (v1v2v3), Pv6v9=7 (v6v7v8v9), Pv3v6=6 (v3v8v7v6), Pv3v9=3 (v3v4v9), Pv1v6和Pv3v9滿足最小性要求， 復制v1v6和v3v4v9的邊，圖中歐拉回路即為所求解。,v2,v4,v5,v7,v8,v10,2,2,1,1,1,1,3,3,v11,3,4,4,1,5,5,6,2,習題十三 5,證明：連通圖G是平面歐拉圖當且僅當其對偶圖是平面二部圖。 證明： “”：當G是平面歐拉圖時，G的點度是偶數(shù)，對應(yīng)G*的面度應(yīng)是偶數(shù)，說明G*的回路都是偶長回路，從而G*是二部圖。 “”：當G*是平面二部圖時，它的面度都是偶

6、數(shù)，因而G的各點度均為偶數(shù)，故G是平面歐拉圖。,n個人定期圍圓桌而坐，商討事務(wù)，他們希望每人每次兩旁的人都和以前的不同，這樣的安排最多有多少種？ 解：將人看作圖的結(jié)點，鄰座關(guān)系作為圖的邊。每次安排方式對應(yīng)一個Hamilton回路。因為每人每次兩旁的人都和以前不同，所以每2種安排方式對應(yīng)2個無公共邊的Hamilton回路。 因每個人都可與其余人鄰座，所以本問題轉(zhuǎn)化為在Kn中找出所有無公共邊的Hamilton回路的個數(shù)。 Kn共有n(n-1)/2條邊，每條Hamilton回路的長度為n，因此Kn中最多有(n-1)/2條無公共邊的Hamilton回路。因此，最多有(n-1)/2種安排。 例如n=7時，共有3種就座方式，分別是： 1 2 3 4 5 6 7 1 1 3 5 7 2 4 6 1 1 4 7 3 6 2 5 1,用2種以上辦法判別下圖不是Hamilton圖。 解： 用必要條件，選7個結(jié)點，去掉后剩9支。 注意觀察，發(fā)現(xiàn)是平面二部圖，因為所有回路都是偶長，那就可對結(jié)點進行二部劃分：一部是7個，另一部是9個