離散數(shù)學(第30講習題課5)

馮偉森Email：fws365@02二月2023離散數(shù)學計算機學院2023/2/2計算機學院2主要內(nèi)容習題課五2023/2/2計算機學院3第十一章深刻理解樹（六個等價命題）及生成樹、樹枝、樹補的定義，掌握生成樹的主要性質(zhì)，并能靈活應用它們；熟練地應用Kruskal算法求最小生成樹；掌握根樹、m叉樹、完全m叉樹、正則m叉樹、最優(yōu)樹的概念,熟練掌握Huffman算法，并使用它求最優(yōu)二叉樹；第十二章深刻理解平面圖、面、對偶圖的定義；熟記歐拉公式和二個平面圖的必要條件,并能使用它們來判斷圖的非平面性；了解庫拉托夫斯基（Kuratowski）定理和細分圖的概念；2023/2/2計算機學院42023/2/2計算機學院5第十三章深刻理解歐拉圖和歐拉道路的定義，對于給定的圖能判斷它是否為歐拉圖或存在歐拉道路；掌握Fleury算法并會用Fleury算法求出歐拉圖中的歐拉回路；理解中國郵遞員問題算法并會用中國郵遞員算法求出無向圖中的歐拉回路；深刻理解哈密頓道路及其哈密頓圖、圖的閉包概念；2023/2/2計算機學院6會用哈密頓圖和含哈密頓道路的充分條件來判斷某些圖是哈密頓圖或是否含有哈密頓道路；會用破壞哈密頓圖的某些必要條件的方法判斷某些圖不是哈密頓圖嚴格區(qū)分哈密頓圖的充分條件和必要條件理解判斷哈密頓圖的充分必要條件了解推銷商問題的分枝定界求解方法2023/2/2計算機學院7例一

證明當每個結(jié)點的度數(shù)大于等于3時，不存在有7條邊的連通簡單平面圖。證明:(反證法)設圖的邊數(shù)m=7

由題意，d(Vi)≥3，Vi為結(jié)點則由握手定理，則∴結(jié)點的個數(shù)不超過4個，而結(jié)點個數(shù)為4的完全圖的邊數(shù)為6,

故應有環(huán)或平行邊，不是簡單連通平面圖。2023/2/2計算機學院8例二

有6個村莊Vi，i=l，2，…，6欲修建道路使村村可通?，F(xiàn)已有修建方案如下帶權(quán)無向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費用，問應選擇修建哪些道路可使得任二個村莊之間是可通的且總修建費用最低?要求寫出求解過程，畫出符合要求的最低費用的道路網(wǎng)絡圖并計算其費用。2023/2/2計算機學院92023/2/2計算機學院1013527V2V6V4V1V3V5費用=182023/2/2計算機學院11例三

設圖G是具有6個頂結(jié)點、12條邊的無向簡單圖,證明圖G是哈密頓圖。證明：已知一個圖是哈密頓圖的充分條件是：圖中任意不同兩點的度數(shù)之和大于等于n。（反證法）假設圖G中存在兩個結(jié)點v1,v2,其度數(shù)之和不大于等于6,即

d(v1)+d(v2)≤5。

2023/2/2計算機學院12而刪去這兩個點后,至多刪去圖G中的5條邊。由于圖G是具有6個頂點,12條邊的無向簡單圖,刪去頂點v1,v2后,得到的子圖為:具有4個結(jié)點,至少7條邊的無向簡單圖,但這樣的無向簡單圖不存在(4階無向簡單圖最多有6條邊),由此證明圖G中任意不同兩點的度數(shù)之和大于等于6,圖G是哈密頓圖。2023/2/2計算機學院131,解：設L是葉的數(shù)目，m是樹的邊數(shù)由握手定理

由樹的定義習題十一2023/2/2計算機學院1413、設簡單連通圖G=（V，E）的邊集E恰好可以分劃為G的兩個生成樹的邊集。證明：如果G中恰有兩個4度以下的結(jié)點u和v，則uvE。證：（反證法）設E=E1∪E2

，E1∩E2=φT（E1），T（E2）是G的兩棵生成樹。如uv∈E，則uv∈E1

或uv∈E2。不妨設uv∈E1，由于T（E1）是G的生成樹，則u或v必有其中一個同其它結(jié)點相鄰，即在T（E1）中，u和v的度數(shù)之和大于等于3.2023/2/2計算機學院15而在T（E2）中，u和v分別同其它結(jié)點相鄰，且相關(guān)聯(lián)的邊∈E2.故在G中，

d(u)+d(v)≥5.∵T（E1），T（E2）是G的兩棵生成樹

∴m（E1）＋m（E2）=2(n-1)

2m(G)=2(m（E1）＋m（E2）)=4(n-1)，由握手定理，4(n-1)≥4(n-2)+5，矛盾所以uv

E。2023/2/2計算機學院1616、證明:在完全二叉樹中，邊的數(shù)目等于2（t-1），式中t是葉的數(shù)目。證明：設葉結(jié)點的個數(shù)為t，分支數(shù)為i，邊的數(shù)目為L，由定理11.5(m-1)i=t-1∵m=2∴i=t-1由完全二叉樹的定義和握手定理，

2L=t+3i-1=t+3(t-1)-1=4t-4∴L=2(t-1)2023/2/2計算機學院1721、

證明:正則二叉樹必有奇數(shù)個結(jié)點。證明：由正則二叉樹的定義，其葉結(jié)點的個數(shù)必為偶數(shù)，設葉數(shù)為t，分支數(shù)為i

由定理11.5(m-1)i=t-1∵m=2∴i=t-1即分支點數(shù)是奇數(shù)故結(jié)點數(shù)n=i+t=奇數(shù)，且n=2t-1，即t=（n+1）/22023/2/2計算機學院18習題十二3、證：（反證法）設G=（n，m）和G′=（n，m′）都是平面圖由G和G′的定義m+m′=n(n-1)/2由定理12.5

m≤3n-6,m′≤3n-6∴m+m′=n(n-1)/2≤6n-12整理上式有n2-13n+24=(n-11)2+9n-97≤0又∵（n-11)2≥0，n≥11時,9n-97≥2∴（n-11)2+9n-97≥2與上式相矛盾，故G與G′至少有一個是非平面圖2023/2/2計算機學院194、證明：具有6個結(jié)點、12條邊的簡單連通平面圖，它的面的度數(shù)都是3。證：由Euler公式，n-m+f=2∴6-12+f=2f=8

即面數(shù)為8，∵對每個面，其度數(shù)≥3∴總面度≥3×8=24∵總面度=2×m=24∴每個面的度數(shù)為32023/2/2計算機學院205、證明：少于30條邊的簡單平面至少有一個頂點的度不大于4。證：（反證法）設所有頂點的度數(shù)≥5由定理12.5m≤3n-6∵

5n/2≤m≤3n-6∴n≥12

則m≥5n/2≥5×12/2=30

與m＜30矛盾∴至少存在一個頂點的度數(shù)不超過42023/2/2計算機學院21習題十三10、證明:4k+l階的所有2k正則簡單圖都是哈密頓圖。證：∵G是2k正則圖，∴對任意的u、v∈G，d(u)+d(v)=4k

由定理13.4,在G中存在一條Hamilton道路，設為：

v1v2,…,v4k+11）v1v4k+1∈E，則v1v2,…,v4k+1v1構(gòu)成一個Hamilton圈。

2）v1v4k+1E，則

2023/2/2計算機學院22∵G的階數(shù)為4k+1∴

（否則d(v4k+1)=4k-1-2k=2k-1

與d(v4k+1)=2k矛盾)

可構(gòu)造即為G的一個Hamilton圈，故G是一個Hamilton圖2023/2/2計算機學院2313、今有n個人,已知他們中的任何二人合起來認識其余的n-2個人。證明:1）當n≥3時,這n個人能排成一列、使得中間的任何人都認識兩旁的人,而站在兩端的人認識左邊(或右邊)的人。2）當n≥4時,這n個人能排成一個圓圈,使得每個人都認識兩旁的人。證明：作n階簡單無向圖G=＜V，E＞,

V=n個人的集合,E={(u,v)︱u,v∈V∧u≠v∧u與v認識}.u,v∈V,2023/2/2計算機學院24(1)若u,v相鄰,則

d(u)+d(v)≥(n-2)+2=n。(2)若u,v不相鄰,則對w∈V-{u,v},w必與u和v都相鄰。否則,比如u和w不相鄰,則v,w都不鄰接u,于是u和w合起來至多與其余的n?3個人認識,與已知條件不符.

因而d(u)+d(v)≥2(n-2)。

1)當n≥3時,2(n-2)≥n-1,因此無論第(1)或(2)種情形,都有

d(u)+d(v)≥n?1,2023/2/2計算機學院25

由定理13.4知G中有哈密頓道路、道路上的人按在道路中的順序排成一列,即滿足要求。

2）當n≥4時,2(n-2)≥n,因此無論第(1)或(2)種情形,都有

d(u)+d(v)≥n,

由定理13.5知G中有哈密頓圈,所有的人按圈