《離散數(shù)學(xué)-圖論復(fù)習(xí)》由會員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)-圖論復(fù)習(xí)(9頁珍藏版)》請在裝配圖網(wǎng)上搜索。
離散數(shù)學(xué)11春圖論部分綜合練習(xí)輔導(dǎo)
大家好!本學(xué)期的第二次教學(xué)輔導(dǎo)活動現(xiàn)在開始,本次活動主要是針對第二單元圖論的重點學(xué)習(xí)內(nèi)容進(jìn)行輔導(dǎo),方式同樣是通過講解一些典型的綜合練習(xí)作業(yè)題目,幫助大家進(jìn)一步理解和掌握圖論的基本概念和方法.
圖論作為離散數(shù)學(xué)的一部分,主要介紹圖論的基本概念、理論與方法.教學(xué)內(nèi)容主要有圖的基本概念與結(jié)論、圖的連通性與連通度、圖的矩陣表示、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹、根樹及其應(yīng)用等.
本次綜合練習(xí)主要是復(fù)習(xí)這一單元的主要概念與計算方法,與集合論一樣,也安排了五種類型,有單項選擇題、填空題,判斷說明題、計算題、證明題.這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型,能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí).
下面是本學(xué)期第4,5次形考作業(yè)中的部分題目.
一、單項選擇題
單項選擇題主要是第4次形考作業(yè)的部分題目.
第4次作業(yè)同樣也是由10個單項選擇題組成,每小題10分,滿分100分.在每次作業(yè)在關(guān)閉之前,允許大家反復(fù)多次練習(xí),系統(tǒng)將保留您的最好成績,希望大家要多練幾次,爭取好成績.需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣,請大家一定要認(rèn)真閱讀題目.
1.設(shè)圖G=
,vV,則下列結(jié)論成立的是 ( ) .
A.deg(v)=2E B. deg(v)=E
C. D.
該題主要是檢查大家對握手定理掌握的情況.復(fù)習(xí)握手定理:
定理3.1.1 設(shè)G是一個圖,其結(jié)點集合為V,邊集合為E,則
也就是說,無向圖G的結(jié)點的度數(shù)之和等于邊數(shù)的兩倍.
正確答案:C
2.設(shè)無向圖G的鄰接矩陣為
,
則G的邊數(shù)為( ).
A.6 B.5 C.4 D.3
主要是檢查對鄰接矩陣的概念理解是否到位.大家要復(fù)習(xí)鄰接矩陣的定義,要記住當(dāng)給定的簡單圖是無向圖時,鄰接矩陣為對稱的.即當(dāng)結(jié)點vi與vj相鄰時,結(jié)點vj與vi也相鄰,所以連接結(jié)點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個1,題中給出的鄰接矩陣中共有10個1,故有102=5條邊.
o
o
o
o
a
b
c
d
o
e
正確答案:B
3.如右圖所示,以下說法正確的是 ( ) .
A.{(a, e)}是割邊
B.{(a, e)}是邊割集
C.{(a, e) ,(b, c)}是邊割集
D.{(d, e)}是邊割集
先復(fù)習(xí)割邊、邊割集的定義:
定義3.2.9 設(shè)無向圖G=為連通圖,若有邊集E1E,使圖G刪除了E1的所有邊后,所得的子圖是不連通圖,而刪除了E1的任何真子集后,所得的子圖是連通圖,則稱E1是G的一個邊割集.若某個邊構(gòu)成一個邊割集,則稱該邊為割邊(或橋)
因為刪除答案A或B或C中的邊后,得到的圖是還是連通圖,因此答案A、B、C是錯誤的.
正確答案:D
o
o
o
a
b
c
d
o
4.圖G如由圖所示,以下說法正確的是 ( ).
A.a(chǎn)是割點
B.{b, c}是點割集
C.{b, d}是點割集
D.{c}是點割集
主要是檢查對點割集、割點的概念理解的情況.
定義3.2.7 設(shè)無向圖G=為連通圖,若有點集V1V,使圖G刪除了V1的所有結(jié)點后,所得的子圖是不連通圖,而刪除了V1的任何真子集后,所得的子圖是連通圖,則稱V1是G的一個點割集.若某個結(jié)點構(gòu)成一個點割集,則稱該結(jié)點為割點.
從圖二中刪除結(jié)點b, c,得到的子圖是由不連通圖,而只刪除結(jié)點b或結(jié)點c,得到的子圖仍然是連通的,由定義可以知道,{b, c}是點割集.所以
正確答案:B
5.設(shè)有向圖(a)、(b)、(c)與(d)如下圖所示,則下列結(jié)論成立的是( ).
A.(a)是強(qiáng)連通的 B.(b)是強(qiáng)連通的
C.(c)是強(qiáng)連通的 D.(d)是強(qiáng)連通的
我們先復(fù)習(xí)強(qiáng)連通的概念:
定義3.2.5 在簡單有向圖中,若在任何結(jié)點偶對中,至少從一個結(jié)點到另一個結(jié)點可達(dá)的,則稱圖G是單向(側(cè))連通的;
若在任何結(jié)點偶對中,兩結(jié)點對互相可達(dá),則稱圖G是強(qiáng)連通的.
正確答案:A
問:上面的圖中,哪個僅為弱連通的?
請大家要復(fù)習(xí)“弱連通”的概念.
6.設(shè)完全圖K有n個結(jié)點(n2),m條邊,當(dāng)( )時,K中存在歐拉回路.
A.m為奇數(shù) B.n為偶數(shù) C.n為奇數(shù) D.m為偶數(shù)
我們先復(fù)習(xí)完全圖的概念:
定義3.1.6 簡單圖G=中,若每一對結(jié)點間都有邊相連,則稱該圖為完全圖.有n個結(jié)點的無向完全圖記為Kn.
由定義可知,完全圖Kn中的任一結(jié)點v到其它結(jié)點都有一條邊,共有n-1條邊,即每個結(jié)點的度數(shù)是n-1,當(dāng)n為奇數(shù)時,n-1為偶數(shù).
由定理4.1.1的推論
一個無向圖具有一條歐拉回路,當(dāng)且僅當(dāng)該圖是連通的,并且它的結(jié)點度數(shù)都是偶數(shù).
所以,正確答案應(yīng)該是C.
7.若G是一個漢密爾頓圖,則G一定是( ).
A.平面圖 B.對偶圖 C.歐拉圖 D.連通圖
我們先復(fù)習(xí)漢密爾頓圖的概念:
定義4.2.1 給定圖G,若存在一條路經(jīng)過圖G的每個結(jié)點一次且僅一次,則該路稱為漢密爾頓路;若存在一條回路經(jīng)過圖G的每個結(jié)點一次且僅一次,則該回路稱為漢密爾頓回路;
具有漢密爾頓回路的圖稱為漢密爾頓圖.
由定義可知,漢密爾頓圖是連通圖.
所以,正確答案應(yīng)該是D.
問:漢密爾頓圖為什么不一定是歐拉圖嗎?
8.設(shè)G是連通平面圖,有v個結(jié)點,e條邊,r個面,則r= ( ).
A.e-v+2 B.v+e-2 C.e-v-2 D.e+v+2
本題主要檢查大家是否掌握了歐拉定理.
定理4.3.2(歐拉定理) 設(shè)連通平面圖G的結(jié)點數(shù)為v,邊數(shù)為e,面數(shù)為r,則歐拉公式v-e+r =2成立.
由歐拉公式v-e+r =2,得到r = e- v+2.
所以,答案A是正確的.
9.無向簡單圖G是棵樹,當(dāng)且僅當(dāng)( ).
A.G連通且邊數(shù)比結(jié)點數(shù)少1 B.G連通且結(jié)點數(shù)比邊數(shù)少1
C.G的邊數(shù)比結(jié)點數(shù)少1 D.G中沒有回路.
可以運用教材中的定理5.1.1,可以作出正確選擇.因為定理5.1.1中給出的圖T為樹的等價定義之一是圖T連通且e=v-1,其中e是邊數(shù),v是結(jié)點數(shù).也就是說:無向簡單圖G是棵樹,當(dāng)且僅當(dāng)G連通且邊數(shù)比結(jié)點數(shù)少1.
正確答案:A
注:由上面的樹的等價定義可知,結(jié)點數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹.
10.已知一棵無向樹T中有8個結(jié)點,4度,3度,2度的分支點各一個,T的樹葉數(shù)為( ).
A.8 B.5 C.4 D.3
正確答案:B
設(shè)無向樹T的樹葉數(shù)為x,因為樹葉是度數(shù)為1的結(jié)點.
那么,由定理3.1.1(握手定理) 設(shè)G是一個圖,其結(jié)點集合為V,邊集合為E,則
得 4+3+2+x=2(8-1),即x=5.應(yīng)選擇B.
下面的內(nèi)容主要是第5次形考作業(yè)的部分題目.
二、填空題
1.已知圖G中有1個1度結(jié)點,2個2度結(jié)點,3個3度結(jié)點,4個4度結(jié)點,則G的邊數(shù)是 .
也是檢查大家對握手定理掌握的情況.
因為圖G中有1個1度結(jié)點,2個2度結(jié)點,3個3度結(jié)點,4個4度結(jié)點,即,根據(jù)握手定理,邊數(shù)有
o
o
o
o
a
b
c
d
o
e
o
f
.
應(yīng)該填寫:15
2.設(shè)給定圖G (如右圖所示),則圖G的點割集是
.
本題還是檢查大家對點割集、割點的概念理解的情
況.
點割集、割點的定義前面已經(jīng)復(fù)習(xí)了,從圖G中刪除結(jié)點f,得到的子圖是不連通圖,即結(jié)點集{f}是點割集;同樣,從圖G中刪除結(jié)點c,e,得到的子圖也是不連通圖,那么結(jié)點集{c, e}也是點割集.而刪除其他結(jié)點集都沒有滿足點割集、定義的集合,所以
應(yīng)該填寫:{f}、{c, e}
3.無向圖G存在歐拉回路,當(dāng)且僅當(dāng)G連通且 .
由定理4.1.1的推論
一個無向圖具有一條歐拉回路,當(dāng)且僅當(dāng)該圖是連通的,并且它的結(jié)點度數(shù)都是偶數(shù).
應(yīng)該填寫:結(jié)點度數(shù)都是偶數(shù)
4.設(shè)G=是具有n個結(jié)點的簡單圖,若在G中每一對結(jié)點度數(shù)之和大于等于 ,則在G中存在一條漢密爾頓路.
定理4.2.2 設(shè)G=是具有n個結(jié)點的簡單圖,若在G中每一對結(jié)點度數(shù)之和大于等于n-1,則在G中存在一條漢密爾頓路.
應(yīng)該填寫:n-1
5.設(shè)圖G是有6個結(jié)點的連通圖,結(jié)點的總度數(shù)為18,則可從G中刪去
條邊后使之變成樹.(……邊后,可以確定圖G的一棵生成樹)
由握手定理(定理3.1.1)知道圖G有182=9 條邊,又由定理5.1.1中給出的圖T為樹的等價定義之一是“圖T連通且e=v-1”,可以知道:
應(yīng)該填寫:4.
6.設(shè)正則5叉樹的樹葉數(shù)為17,則分支數(shù)為i = .
定理5.2.1 設(shè)有正則m叉樹,其樹葉數(shù)為t,分枝數(shù)為i,則(m-1)i=t-1.
其中m=5, t=17,由(5-1)i=17-1,得i =4.
應(yīng)該填寫:4
三、判斷說明題
1.如果圖G是無向圖,且其結(jié)點度數(shù)均為偶數(shù),則圖G存在一條歐拉回路.
分析:先復(fù)習(xí)歐拉圖的判別定理:
定理4.1.1的推論:一個無向圖具有一條歐拉回路,當(dāng)且僅當(dāng)該圖是連通的,并且它的結(jié)點度數(shù)都是偶數(shù).
解:不正確.
因為題中的圖G沒有“連通”的條件.
2.如下圖所示的圖G存在一條歐拉回路.
解:不正確.
因為圖G中結(jié)點b和c的度數(shù)是奇數(shù).
注:這是一個漢密爾頓圖,但不是歐拉圖,它可以作為單向選擇題7解答之后提出的問題的一個解答.
3.設(shè)G是一個有7個結(jié)點16條邊的連通圖,則G為平面圖.
分析:定理4.3.3 設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖,若v≥3,則e≤3v-6.
利用該定理判斷本題.
解:不正確.
因為題中的連通簡單平面圖有v=7個結(jié)點,e=16條邊,那么1637-6=15,由定理4.3.3知道,圖G不是平面圖.
4.設(shè)G是一個連通平面圖,且有6個結(jié)點11條邊,則G有7個面.
分析:可以用平面圖中的歐拉公式:v-e+r =2來判斷,其中v為結(jié)點數(shù),e為邊數(shù),r為面數(shù).
解:正確.
因為連通平面圖G有v=6個結(jié)點,e=11條邊,那么由歐拉公式計算得:r =2+ 11- 6 = 7個面.
四、計算題
1.設(shè)G=,V={ v1,v2,v3,v4,v5},E={ (v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5) },試
(1) 給出G的圖形表示; (2) 寫出其鄰接矩陣;
(3) 求出每個結(jié)點的度數(shù); o
o
o
o
v1
o
v5
v2
v3
v4
(4) 畫出其補(bǔ)圖的圖形.
解:(1) 因為V={ v1,v2,v3,v4,v5},
E={ (v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),
(v4,v5) },所以G的圖形表示為:
(2) 分析:本題給定的簡單圖是無向圖,
因此鄰接矩陣為對稱的.即當(dāng)結(jié)點vi與vj相
鄰時,結(jié)點vj與vi也相鄰,所以連接結(jié)點vi
與vj的一條邊在鄰接矩陣的第i行第j列處和
第j行第i列處各寫一個1;當(dāng)結(jié)點vi與vj沒
有邊連接時,鄰接矩陣的第i行第j列處和第j行第i列處各寫一個0.
鄰接矩陣:
(3) 由G的圖形可知,v1,v2,v3,v4,v5結(jié)點的度數(shù)依次為1,2,4,3,2
o
o
o
o
v1
o
v5
v2
v3
v4
o
o
o
o
v1
o
v5
v2
v3
v4
(4) 由關(guān)于補(bǔ)圖的定義3.1.9可知,先畫出完全圖(見圖1),然后去掉原圖,可得補(bǔ)圖(見圖2)如下:
圖1 圖2
注意:補(bǔ)圖中,如果沒有標(biāo)出結(jié)點v3,則是錯的.
2.圖G=,其中V={ a, b, c, d, e},E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) },對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5,試
(1)畫出G的圖形; (2)寫出G的鄰接矩陣;
(3)求出G權(quán)最小的生成樹及其權(quán)值.
解 (1)因為V={ a, b, c, d, e},E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) },所以G的圖形表示為:
(2)由圖得圖G的鄰接矩陣為:
(3)圖G有5個結(jié)點,其生成樹有4條邊,用Kruskal算法(避圈法)求其權(quán)最小的生成樹T:
第1步,取具最小權(quán)1的邊(a, c);
第2步,取剩余邊中具最小權(quán)1的邊(c, e);
第3步,取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)2的邊(a, b);
第4步,取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)3的邊(b, d).
所求最小生成樹T如右下圖,其權(quán)為.
注意:在用避圈法求最小的生成樹的關(guān)鍵是:“取圖中權(quán)數(shù)最小的邊,且與前面取到的邊不構(gòu)成圈”,很多學(xué)生只注意到取權(quán)數(shù)最小的邊了,而忽略了“不構(gòu)成圈”的要求.
如果結(jié)點數(shù)少一個,邊數(shù)也少些,大家應(yīng)該會做了吧.
3.設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31,試畫出相應(yīng)的最優(yōu)二叉樹,計算該最優(yōu)二叉樹的權(quán).
解:方法(Huffman):從2, 3, 5, 7, 17, 31中選2, 3為最低層結(jié)點,并從權(quán)數(shù)中刪去,再添上他們的和數(shù),即5, 5, 7, 17, 31;
o
o
o
o
o
3
2
7
5
5
17
34
10
o
o
o
o
17
31
o
o
65
再從5, 5, 7, 17, 31中選5, 5為倒數(shù)第2層結(jié)點,并從
上述數(shù)列中刪去,再添上他們的和數(shù),即7, 10, 17, 31;
然后,從7, 10, 17, 31中選7, 10為倒數(shù)第3層結(jié)點,
并從上述數(shù)列中刪去,再添上他們的和數(shù),即17, 17, 31;
……
最優(yōu)二叉樹如右圖所示.
最優(yōu)二叉樹權(quán)值為:25+35+54+73+172+311
=10+15+20+21+34+31=131
講評:作業(yè)中最優(yōu)二叉樹往往都能畫對了,但計算總權(quán)值時
可能會把有些權(quán)的層數(shù)計算錯了,導(dǎo)致總權(quán)值計算錯誤,大家一定要細(xì)心.
注意:這3個計算題大家一定要掌握.
五、證明題
證明題同學(xué)一般都做不好,原因是對證明題方法沒有掌握,也是對一些概念不清楚所造成的.因此,希望大家認(rèn)真學(xué)習(xí)教材和老師講課中的證明方法,并通過作業(yè)逐步掌握做證明題的方法.
1.設(shè)G是一個n階無向簡單圖,n是大于等于3的奇數(shù).證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點個數(shù)相等.
證明:設(shè),.則是由n階無向完全圖的邊刪去E所得到的.所以對于任意結(jié)點,u在G和中的度數(shù)之和等于u在中的度數(shù).由于n是大于等于3的奇數(shù),從而的每個結(jié)點都是偶數(shù)度的(度),于是若在G中是奇數(shù)度結(jié)點,則它在中也是奇數(shù)度結(jié)點.故圖G與它的補(bǔ)圖中的奇數(shù)度結(jié)點個數(shù)相等.
2.設(shè)連通圖G有k個奇數(shù)度的結(jié)點,證明在圖G中至少要添加條邊才能使其成為歐拉圖.
證明:由定理3.1.2,任何圖中度數(shù)為奇數(shù)的結(jié)點必是偶數(shù),可知k是偶數(shù).
又根據(jù)定理4.1.1的推論,圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點.因此只要在每對奇數(shù)度結(jié)點之間各加一條邊,使圖G的所有結(jié)點的度數(shù)變?yōu)榕紨?shù),成為歐拉圖.
故最少要加條邊到圖G才能使其成為歐拉圖.
9
鏈接地址:http://m.jqnhouse.com/p-10477515.html