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

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

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

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

有6個(gè)村莊Vi，i=l，2，…，6欲修建道路使村村可通?，F(xiàn)已有修建方案如下帶權(quán)無(wú)向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費(fèi)用，問(wèn)應(yīng)選擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總修建費(fèi)用最低?要求寫(xiě)出求解過(guò)程，畫(huà)出符合要求的最低費(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個(gè)頂結(jié)點(diǎn)、12條邊的無(wú)向簡(jiǎn)單圖,證明圖G是哈密頓圖。證明：已知一個(gè)圖是哈密頓圖的充分條件是：圖中任意不同兩點(diǎn)的度數(shù)之和大于等于n。（反證法）假設(shè)圖G中存在兩個(gè)結(jié)點(diǎn)v1,v2,其度數(shù)之和不大于等于6,即

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

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

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

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

或uv∈E2。不妨設(shè)uv∈E1，由于T（E1）是G的生成樹(shù)，則u或v必有其中一個(gè)同其它結(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的兩棵生成樹(shù)

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

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

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

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

證明:正則二叉樹(shù)必有奇數(shù)個(gè)結(jié)點(diǎn)。證明：由正則二叉樹(shù)的定義，其葉結(jié)點(diǎn)的個(gè)數(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時(shí),9n-97≥2∴（n-11)2+9n-97≥2與上式相矛盾，故G與G′至少有一個(gè)是非平面圖2023/2/2計(jì)算機(jī)學(xué)院194、證明：具有6個(gè)結(jié)點(diǎn)、12條邊的簡(jiǎn)單連通平面圖，它的面的度數(shù)都是3。證：由Euler公式，n-m+f=2∴6-12+f=2f=8

即面數(shù)為8，∵對(duì)每個(gè)面，其度數(shù)≥3∴總面度≥3×8=24∵總面度=2×m=24∴每個(gè)面的度數(shù)為32023/2/2計(jì)算機(jī)學(xué)院205、證明：少于30條邊的簡(jiǎn)單平面至少有一個(gè)頂點(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矛盾∴至少存在一個(gè)頂點(diǎn)的度數(shù)不超過(guò)42023/2/2計(jì)算機(jī)學(xué)院21習(xí)題十三10、證明:4k+l階的所有2k正則簡(jiǎn)單圖都是哈密頓圖。證：∵G是2k正則圖，∴對(duì)任意的u、v∈G，d(u)+d(v)=4k

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

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

V=n個(gè)人的集合,E={(u,v)︱u,v∈V∧u≠v∧u與v認(rèn)識(shí)}.u,v∈V,2023/2/2計(jì)算機(jī)學(xué)院24(1)若u,v相鄰,則

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

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

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

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

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

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

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

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