【文章內(nèi)容簡介】 個連通分支，分別為n1,n2階連通無向簡單子圖，則n1+n2≤n。對G1中任意結(jié)點v1,和G2中任意結(jié)點v2而言，v1的最大點度為n11,v2的最大結(jié)點度為n21。則v1,v2的點度之和，最大為n1+n22≤n2。矛盾的導出，是因為假設(shè)G不是連通圖引起的，因此，原題設(shè)結(jié)論成立■30. 、可達性矩陣、強分圖和關(guān)聯(lián)矩陣。解：對圖的結(jié)點和邊進行編號如下：ｅ１２ｅ１１ｅ１０ｅ９ｅ８ｅ７ｅ６ｅ５ｅ３ｅ２ｅ１ｅ４ｖ７ｖ１ｖ３ｖ６ｖ５ｖ４ｖ２鄰接矩陣：　　　因此可達矩陣為：強分圖矩陣為：關(guān)聯(lián)矩陣為：■31. 設(shè)P= (pij) nn是可達性矩陣。證明:PPT中第i行中非零元素所在列號給出了包含結(jié)點vi的強分圖的全部結(jié)點編號。證明：根據(jù)強分矩陣的計算過程可知，其包含的含義是結(jié)點間雙向可達信息。根據(jù)有向圖的雙向可達關(guān)系是一個等價關(guān)系，因此PPT中第i行中非零元素所在列號既是一個等價類，所以包含了一個強分圖的所有結(jié)點■已完成[1，2，3，4，5，6，7，8，9，10，11，12，13,14，15，16，17，18，19，２０,21，２３，２４，２５，２６，２７，２８，29，３０，31]第２２題未證明習題十一1. 設(shè)一個樹中度為k的結(jié)點數(shù)是nk（2≤k），求它的葉的數(shù)目。解：設(shè)T的節(jié)點總數(shù)為n，葉節(jié)點數(shù)目為t ，根據(jù)題意及握手定理有： t + n2 + n3 + …+ nk = n (1) t + 2n2 + 3n3 + …k(nk) = 2(n1) (2) 握手定理(1),(2)聯(lián)立求解得： t = n3 + 2n4 + … (k2)nk + 2■2. 證明：樹T中最長道路的起點和終點必都是T的葉。證明：假設(shè)T中最長道路P=vi1vi2…vik的起點或終點不是T的葉結(jié)點，設(shè)d(vi1)1,則vi1的所有鄰接點(v‘1,v’2…,v’l)都在P中，那么在T中可以找到一個回路,那么截取道路P, 得到回路C= vi1 …v’l vi1 .與T中無回路矛盾。對于d(vik)1時同理。因此，假設(shè)不成立，即最長道路P的起點和終點都是T的葉節(jié)點■3. n（n≥3）階無向樹T的最大度Δ至少為幾？最多為幾？解：當T中只有一個枝點時，Δ = n1,為最大值。 當T構(gòu)成一條鏈時，只有兩個葉結(jié)點，其余結(jié)點都為2度點，此時Δ = 2，為最小值，因此Δ至少為2 ，最大為n1■4. n（n≥3）階無向樹T的最大度Δ=2，則T中最長的簡單道路為幾？解：根據(jù)第3題結(jié)論，當無向樹T的最大度Δ=2時 ，T構(gòu)成一條鏈，以此最長的簡單道路包含所有的節(jié)點，道路長度L=n1■5. 證明：任何無向樹都是二部圖。證明：以樹Ｔ中任意結(jié)點ｕ為起點，將與ｕ最短距離為偶數(shù)的結(jié)點放入ｖ１結(jié)點集合，將與ｕ最短距離為奇數(shù)的結(jié)點放入ｖ２結(jié)點集合，那么這兩個結(jié)點集合中，顯然不存在公共點，同時兩個結(jié)點集合組成了樹的全部結(jié)點，因此是數(shù)Ｔ的結(jié)點集合的一個分化。假設(shè)在Ｖｉ集合中存在兩個結(jié)點ｕ１，ｕ２是鄰結(jié)點，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ，其中ｐ１＝ｕ．．．ｕ１代表ｕ到ｕ１的最短路徑，ｐ２＝ｕ２．．．ｕ代表ｕ到ｕ２的最短路徑，且ｕ１ｕ２邊不在最短路徑上，否則他們的最短路徑不是同奇偶的；因此，Ｐ中包含圈，這與樹中無圈相矛盾，所以Ｔ中的邊，只能存在于兩個點集合之間，所以是二部圖■6. 證明：如果T是樹且Δ≥k，則T中至少有k個葉結(jié)點。證明：當T為非平凡樹時，根據(jù)T的定義，T中每個枝點都是割點，當刪除d(v)= Δ 的節(jié)點時，ω（Tv）=Δ ，每個分支都是數(shù)，如果分支都是平凡樹，則這些節(jié)點都是T的葉，葉節(jié)點數(shù)為Δ。如果分支有非平凡數(shù)，那么至少有兩個葉節(jié)點，其中至少一個是刪除v時就存在的，因此總的葉節(jié)點個數(shù)≥Δ≥k。因此Ｔ中至少有ｋ個葉結(jié)點■7. 設(shè)G為n（n≥3）階簡單圖，證明G或中必含圈。（有誤，4,p223）證明：反證法，假設(shè)G和中都不含圈，那么G和的所有分支都是樹。則G所包含的最大邊數(shù)|E(G)|=n1, 則所包含的最大邊數(shù)|E()|=n1. 因為G及的邊數(shù)總和|E(G)|+ |E()| = n(n1)/2, 但根據(jù)假設(shè)條件，max|E(G)|+max |E()|=2(n1) n(n1)/2, ，G或中必含圈■8．證明：恰好有兩個頂點的度為1的樹必為一道路P。證明：因為此樹僅有2個葉結(jié)點，因此Δ3。那么枝點的度只能為2。所以此樹為一條鏈，及一條道路■9. 設(shè)T是一個n+1階樹，G是最小點度的簡單圖。證明：Ｇ必含有與Ｔ同構(gòu)的子圖。證明：采用歸納法證明，對ｎ進行歸納（１） 當ｎ＝１時，Ｔ為２階樹，因為Ｇ是最小點度的簡單圖，所以任意意個結(jié)點與其鄰結(jié)點都構(gòu)成一顆２階樹，成立（２） 假設(shè)ｎ＝ｋ，ｋ≥２時，結(jié)論成立，即T是一個ｋ+1階樹，G是最小點度的簡單圖。Ｇ必含有與Ｔ同構(gòu)的子圖（３） 當ｎ＝ｋ＋１時，G是最小點度的簡單圖，Ｔ是任意一棵ｋ＋２階樹，在Ｔ中刪除一個葉結(jié)點ｔ，那么Ｔ－｛ｔ｝是一棵ｋ＋１ 階樹，利用歸納假設(shè)，G中必存在與Ｔ－｛ｔ｝同構(gòu)的子圖T’，T’中最大的點度不超過k，所以每個T’中的結(jié)點都有鄰結(jié)點不包含在T’中，所以T’可在某個結(jié)點上增加一個額外的結(jié)點u，使T’+{u} 與T 同構(gòu)綜上所述，結(jié)論成立■。證明：e是G的割邊當且僅當e含于G的每個生成樹中。證明：1）充分性：e是G的割邊則e含于G的每個生成樹中假設(shè)e不包含在某棵生成樹T中，那么e 一定在T的樹補邊集中，那么G{e }中依然包含樹T,因此G{e }連通，與e是割邊矛盾，因此e含于G的每個生成樹中；2)　必要性：e含于G的每個生成樹中則e是G的割邊假設(shè)ｅ不是Ｇ的割邊，那么Ｇ－｛ｅ｝依然連通，具有生成樹，這些生成樹也是Ｇ的生成樹，且不包含ｅ，與e含于G的每個生成樹中前提矛盾，因此e是G的割邊。綜上所述，題設(shè)結(jié)論：e是G的割邊當且僅當e含于G的每個生成樹中成立■，a是在T1中但不在T2中的一條邊。證明：T2中存在一條邊b，使得（T1a）+b和（T2b）+a也是G的兩個不同的生成樹。證明：從T1中刪除邊ａ，得樹T1－１和T1－２　，分別用Ｖ１，Ｖ２　表示這兩棵子樹的結(jié)點集合，設(shè)Ea＝｛ｅ｜ｅ的兩個端點分別屬于Ｖ１，Ｖ２｝，顯然，ａ∈Ea．因為ａ不在T2中，所以ａ是T2的樹補邊。設(shè)C（a）為在中T2增加邊a后所得到的圈，則C(a)中必然存在T2 的樹邊b不在T1中但在Ea中。否則，C(a)上的T2的所有樹邊均在T1中或均不在Ea中。如果C(a)上的T2的所有樹邊均在T1中，則C(a)上的所有邊都在T1中，與T1是樹矛盾。如果C(a)上的T2的所有樹邊均不在Ea中，則C(a)中除ａ外所有的邊的端點均在Ｖ１或Ｖ２中，與C(a)是基本回路矛盾。所以C(a)中必然存在不在T1中但在T2中的的樹邊，設(shè)ｂ是其中的一條。則（T1a）+b連通且無回路是Ｇ的生成子圖，它是Ｇ的生成樹。同理（T2b）+a也是Ｇ的生成樹■。解：略，請參考書中算法計算■13. 設(shè)簡單連通圖G=（V，E）的邊集E恰好可以劃分為G的兩個生成樹的邊集。證明：如果G中恰有兩個4度以下結(jié)點u和v，則uvE。（請馮老師幫助證明下）14. 已知n階m條邊的無向簡單圖是由k（k≥2）棵樹組成的森林，證明：m = n – k。證明：設(shè)ｋ棵樹分別為ｎ１，ｎ２，．．．ｎｋ，根據(jù)樹的性質(zhì)有如下公式成立： n 1+n2…nk = n (1) (n 11)+(n21)…(nk1) = m (2)(1)(2) 得：n – m = k = m = nk■15. 證明: 簡單連通無向圖G的任何一條邊，都是G的某一棵生成樹的邊。證明：簡單連通無向圖G的任何一條邊，要么是割邊，要么是非割邊。如果是割邊，那么此邊是所有生成樹的樹邊；如果不是割邊，設(shè)邊為ｅ，那么G{e}連通，可以求出生存樹Ｔ，此Ｔ也是Ｇ的生存數(shù)，且不包含ｅ　，那么ｅ　是Ｔ的樹補邊。則Ｔ+{e},有唯一一個圈Ｃ，刪除圈上任意一條非ｅ邊，便得到一顆包含ｅ邊的樹■16. 證明:在完全二又樹中,邊的數(shù)目等于2(t 1)，式中t是葉的數(shù)目。證明：設(shè)Ｔ中的結(jié)點數(shù)為ｎ，枝點數(shù)為ｉ；根據(jù)完全二叉樹的定義，有下面的等式成立。n=i+t,m=2i,m=，得到m=2(t1) ■17. 決定一個m叉樹中內(nèi)部道路長度之