離散數(shù)學(xué)(第30講習(xí)題課5)

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

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

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

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

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

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

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

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

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

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

或uv∈E2。不妨設(shè)uv∈E1，由于T（E1）是G的生成樹，則u或v必有其中一個同其它結(jié)點(diǎn)相鄰，即在T（E1）中，u和v的度數(shù)之和大于等于3.2023/2/2計(jì)算機(jī)學(xué)院15而在T（E2）中，u和v分別同其它結(jié)點(diǎn)相鄰，且相關(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計(jì)算機(jī)學(xué)院1616、證明:在完全二叉樹中，邊的數(shù)目等于2（t-1），式中t是葉的數(shù)目。證明：設(shè)葉結(jié)點(diǎn)的個數(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計(jì)算機(jī)學(xué)院1721、

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

由定理11.5(m-1)i=t-1∵m=2∴i=t-1即分支點(diǎn)數(shù)是奇數(shù)故結(jié)點(diǎn)數(shù)n=i+t=奇數(shù)，且n=2t-1，即t=（n+1）/22023/2/2計(jì)算機(jī)學(xué)院18習(xí)題十二3、證：（反證法）設(shè)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計(jì)算機(jī)學(xué)院194、證明：具有6個結(jié)點(diǎn)、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計(jì)算機(jī)學(xué)院205、證明：少于30條邊的簡單平面至少有一個頂點(diǎn)的度不大于4。證：（反證法）設(shè)所有頂點(diǎn)的度數(shù)≥5由定理12.5m≤3n-6∵

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

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

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

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

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

2）v1v4k+1E，則

2023/2/2計(jì)算機(jī)學(xué)院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計(jì)算機(jī)學(xué)院2313、今有n個人,已知他們中的任何二人合起來認(rèn)識其余的n-2個人。證明:1）當(dāng)n≥3時,這n個人能排成一列、使得中間的任何人都認(rèn)識兩旁的人,而站在兩端的人認(rèn)識左邊(或右邊)的人。2）當(dāng)n≥4時,這n個人能排成一個圓圈,使得每個人都認(rèn)識兩旁的人。證明：作n階簡單無向圖G=＜V，E＞,

V=n個人的集合,E={(u,v)︱u,v∈V∧u≠v∧u與v認(rèn)識}.u,v∈V,2023/2/2計(jì)算機(jī)學(xué)院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個人認(rèn)識,與已知條件不符.

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

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

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

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

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

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

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