自考 離散數(shù)學(xué)教材課后題第五章答案

千里之行，始于足下。第2頁(yè)/共2頁(yè)精品文檔推薦自考離散數(shù)學(xué)教材課后題第五章答案5.1習(xí)題參考答案

1、設(shè)無(wú)向圖G有16條邊，有3個(gè)4度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)均小于3，咨詢：G中至少有幾個(gè)結(jié)點(diǎn)。

阮允準(zhǔn)同學(xué)提供答案:

解：設(shè)度數(shù)小于3的結(jié)點(diǎn)有x個(gè)，則有

3×4＋4×3＋2x≥2×16

解得：x≥4

因此度數(shù)小于3的結(jié)點(diǎn)至少有4個(gè)

因此G至少有11個(gè)結(jié)點(diǎn)

2、設(shè)無(wú)向圖G有9個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度數(shù)別是5算是6，證明：G中至少有5個(gè)6度結(jié)點(diǎn)或至少有6個(gè)5度結(jié)點(diǎn)。

阮允準(zhǔn)同學(xué)答案：

證明：由題意可知：度數(shù)為5的結(jié)點(diǎn)數(shù)只能是0,2，4,6，8。

若度數(shù)為5的結(jié)點(diǎn)數(shù)為0,2，4個(gè)，則度數(shù)為6的結(jié)點(diǎn)數(shù)為9，7,5個(gè)結(jié)論成立。

若度數(shù)為5的結(jié)點(diǎn)數(shù)為6,8個(gè)，結(jié)論顯然成立。

由上可知，G中至少有5個(gè)6度點(diǎn)或至少有6個(gè)5度點(diǎn)。

3、證明：簡(jiǎn)單圖的最大度小于結(jié)點(diǎn)數(shù)。

阮同學(xué)以為題中應(yīng)指定是無(wú)向簡(jiǎn)單圖.

曉津證明如下：設(shè)簡(jiǎn)單圖有n個(gè)結(jié)點(diǎn)，某結(jié)點(diǎn)的度為最大度，因?yàn)楹?jiǎn)單圖任一結(jié)點(diǎn)沒(méi)有平行邊，而任一結(jié)點(diǎn)的的邊必連有另一結(jié)點(diǎn)，則其最多有n-1條邊與其他結(jié)點(diǎn)相連，所以其度數(shù)最多惟獨(dú)n-1條，小于結(jié)點(diǎn)數(shù)n.

4、設(shè)圖G有n個(gè)結(jié)點(diǎn)，n+1條邊，證明：G中至少有一具結(jié)點(diǎn)度數(shù)≥3。

阮同學(xué)給出證明如下：

證明：設(shè)G中所有結(jié)點(diǎn)的度數(shù)都小于3，即每個(gè)結(jié)點(diǎn)度數(shù)都小于等于2，則所有結(jié)點(diǎn)度數(shù)之和小于等于2n，因此G的邊數(shù)必小于等于n，這和已知G有n+1條邊相矛盾。因此結(jié)論成立。

5、試證明下圖中兩個(gè)圖別同構(gòu)。

曉津證明：同構(gòu)的充要條件是兩圖的結(jié)點(diǎn)和邊分不存在一一對(duì)應(yīng)且保持關(guān)聯(lián)關(guān)系。我們能夠看出，(a)圖和(b)圖中都有一具三度結(jié)點(diǎn)，(a)圖中三度結(jié)點(diǎn)的某條邊關(guān)聯(lián)著兩個(gè)一度結(jié)點(diǎn)和一具二度結(jié)點(diǎn)，而(b)圖中三度結(jié)點(diǎn)關(guān)聯(lián)著兩個(gè)二度結(jié)點(diǎn)和一具一度結(jié)點(diǎn)，所以可斷定二圖別是同構(gòu)的。

6、畫(huà)出所有5個(gè)結(jié)點(diǎn)3條邊，以及5個(gè)結(jié)點(diǎn)7條邊的簡(jiǎn)單圖。

解：如下圖所示：(曉津與阮同學(xué)答案一致)

7、證明：下圖中的圖是同構(gòu)的。

證明如下：

在兩圖中我們能夠看到有

a→e,b→h,c→f,d→g

兩圖中存在結(jié)點(diǎn)與邊的一一對(duì)應(yīng)關(guān)系，并保持關(guān)聯(lián)關(guān)系。

8、證明：下面兩圖是同構(gòu)的。

阮同學(xué)給出證明如下：

證明：找出對(duì)應(yīng)關(guān)系：aq,br,cs,dt,eu,

fv,gw,hx

9、證明：三次正則圖必有偶數(shù)個(gè)結(jié)點(diǎn)。

阮同學(xué)證明如下：

由題意可知每個(gè)結(jié)點(diǎn)度數(shù)基本上3度，即每個(gè)結(jié)點(diǎn)均為奇結(jié)點(diǎn)，依照有偶數(shù)個(gè)奇結(jié)點(diǎn)可知，三次正則圖必有偶數(shù)個(gè)奇結(jié)點(diǎn)。

5.2習(xí)題參考答案

1、給定圖G，如下圖所示，求出G中從A到F的所有初級(jí)路。

解：從A到F的初級(jí)路有：

ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF

2、給定圖G，如下圖所示，找到G中從v2動(dòng)身的所有初級(jí)回路。

曉津以為圖中少了一具箭頭：從V1到V2有一箭頭。

從V2動(dòng)身的初級(jí)回路有：V2V4V1V2、V2V3V4V1V2.

3、設(shè)G為無(wú)向連通圖，有n個(gè)結(jié)點(diǎn)，這么G中至少有幾條邊？為啥？對(duì)有向圖怎么？

解：若G為無(wú)向連通圖，有n個(gè)結(jié)點(diǎn)，則G中至少有n-1條邊。因?yàn)樵趎個(gè)結(jié)點(diǎn)的圖中，任取一具結(jié)點(diǎn)為起始點(diǎn)，若要連通其他每個(gè)結(jié)點(diǎn)，則其他每個(gè)結(jié)點(diǎn)至少應(yīng)有1度,此結(jié)點(diǎn)則有n-1度。所以總的度數(shù)至少為2n-2度，而度數(shù)為邊的2倍，可算得邊數(shù)為n-1.

關(guān)于有向圖，若是弱連通，則與無(wú)向圖一樣至少為n-1,若是單側(cè)連通也是這樣，而強(qiáng)連通邊數(shù)至少為n。(此題依照阮允準(zhǔn)同學(xué)的答案更正)

4、設(shè)V'和E'分不為無(wú)向連通圖G的點(diǎn)割集和邊割集，G-E'的連通分支數(shù)一定是多少？G-V'的連通分支數(shù)也是定數(shù)嗎?

解：

G-E'的連通分支數(shù)一定是2，而G-V'的連通分支數(shù)就別是定數(shù)了。有也許大于2.

5、設(shè)有七人a,b,c,d,e,f,g,已知：a會(huì)說(shuō)英語(yǔ)，b會(huì)說(shuō)漢語(yǔ)和英語(yǔ)，c會(huì)說(shuō)英語(yǔ)、意大利語(yǔ)和俄語(yǔ)，d會(huì)說(shuō)日語(yǔ)和漢語(yǔ),e會(huì)說(shuō)德語(yǔ)和意大利語(yǔ)，f會(huì)說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)，g會(huì)說(shuō)法語(yǔ)和德語(yǔ)，試咨詢這七人間能夠任意交談嗎？

答：能夠。設(shè)七個(gè)人為圖中的7個(gè)結(jié)點(diǎn)，以他們之間有共同語(yǔ)言為條件畫(huà)邊，能夠看出，七個(gè)人的結(jié)點(diǎn)在圖中是連通的，所以這七個(gè)人間能夠經(jīng)過(guò)相互翻譯任意交談。

6、一具有向圖是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一具回路，它至少包含每個(gè)結(jié)點(diǎn)一次。

證明如下：

必要性：假如圖中的任何一具回路都別能包含所有結(jié)點(diǎn),則可知未被包含在回路內(nèi)的結(jié)點(diǎn)別能與其他結(jié)點(diǎn)中的某一結(jié)點(diǎn)連通。這與本圖是強(qiáng)連通的相矛盾。所以必有如此一具路它至少包含每個(gè)結(jié)點(diǎn)一次。

充分性：當(dāng)G中有一具回路，它至少包含每個(gè)結(jié)點(diǎn)一次時(shí)，能夠懂，任一結(jié)點(diǎn)可達(dá)其他所有結(jié)點(diǎn)，所以它是強(qiáng)連通的。

7、若有簡(jiǎn)單圖至多有2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)度數(shù)至少為n，G是連通圖。

又若簡(jiǎn)單圖G至多有2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)度數(shù)至少為n-1，這么G是連通圖嗎？為啥？

答：G別再是連通圖，假若n=1時(shí)，G中至多可有2個(gè)結(jié)點(diǎn)，而每個(gè)結(jié)點(diǎn)度數(shù)至少能夠?yàn)?，顯然這兩個(gè)結(jié)點(diǎn)別能連通。

以下是阮同學(xué)的答案：

辦法一：設(shè)v1、v2是那個(gè)簡(jiǎn)單圖的任意兩個(gè)結(jié)點(diǎn)，由已知可得，v1、v2的度數(shù)至少為n，

（1）若v1、v2之間有邊，則顯然v1、v2是連通的。

（2）若v1、v2無(wú)邊，則v1和剩下的結(jié)點(diǎn)中的n個(gè)結(jié)點(diǎn)有邊相連，v2也和剩下的結(jié)點(diǎn)中的n個(gè)結(jié)點(diǎn)有邊相連。因?yàn)槭Ｏ碌慕Y(jié)點(diǎn)最多惟獨(dú)2n-2個(gè)，由抽屜原理可得，至少存在一具結(jié)點(diǎn)，它和v1、v2都有邊相連，此刻v1和v2也是連通的。

由（1）（2）可知，結(jié)論成立

辦法二：顯然那個(gè)圖中任意的一對(duì)結(jié)點(diǎn)的度數(shù)之和大于等于2n，因此那個(gè)圖是漢密爾頓圖，因此那個(gè)圖是連通的。

8、簡(jiǎn)單圖G有n個(gè)結(jié)點(diǎn)，e條邊，設(shè)e>0.5(n-1)(n-2),證明：G是連通的。

證明如下：n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向圖，連通的最低條件是有n-1條邊。而

e>0.5(n-1)(n-2)

可得e≥n-1，所以G是連通的。

上面的答案是錯(cuò)誤的，阮允準(zhǔn)同學(xué)糾正如下：因?yàn)橐痪哌B通圖至少要有n-1條邊，但并別是講至少有n-1條邊的圖一定是連通圖。同時(shí)容易驗(yàn)證那個(gè)結(jié)論別成立。

證明如下：

在圖G中，它的結(jié)點(diǎn)數(shù)為n，設(shè)v是G中任一結(jié)點(diǎn)，若把v去掉后，其它n-1結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)度數(shù)最多有n-1度，所以n-1個(gè)結(jié)點(diǎn)之間最多惟獨(dú)0.5（n-1)(n-2)條邊，而e＞0.5(n-1)(n-2),因此至少有一條邊連接v和其它結(jié)點(diǎn)。

下面我用數(shù)學(xué)歸納法進(jìn)一步證明：

（1）容易證明當(dāng)n=1,2時(shí)，結(jié)論成立

（2）假設(shè)當(dāng)n=k時(shí)，結(jié)論成立，即若e＞0.5（k-1)(k-2)時(shí)結(jié)論成立

（3）當(dāng)n=k+1時(shí)，若此刻每個(gè)結(jié)點(diǎn)度數(shù)為k，則結(jié)論顯然成立，否則必存在一具結(jié)點(diǎn)v度數(shù)至多惟獨(dú)k-1度，即那個(gè)結(jié)點(diǎn)最多惟獨(dú)k-1條邊和它相連。因?yàn)榇丝炭偟倪厰?shù)e>0.5k(k-1),則其它k個(gè)結(jié)點(diǎn)之間的邊數(shù)e'＞

0.5k(k-1)-(k-1)=0.5(k-1)(k-2)。依照歸納假設(shè)，顯然這k個(gè)結(jié)點(diǎn)之間是連通的，而依照上面我們懂，至少有一條邊使v和其它結(jié)點(diǎn)相連，因此此刻那個(gè)圖是連通的。

依照（1）（2）（3）可知結(jié)論成立。

5.3習(xí)題參考答案

1、設(shè)圖G=,V={v1,v2,v3,v4}的鄰接矩陣

則v1的入度deg(v1)是多少？v4的出度deg(v4)是多少？從v1到v4長(zhǎng)度為2的路有幾條？

解：1、v1的入度是3.

v4的出度是1，

因?yàn)?/p>

A2(G)=2011

22011112

0101

因此從v1到v4長(zhǎng)度為2的路有1條。

2、有向圖G如圖所示，求G中長(zhǎng)度為4的路徑總數(shù)，并指出其中有多少條是回路。v3到v4的跡有幾條。

答：長(zhǎng)度為4的路徑總數(shù)為15條，其中3條

是回路。從v3到v4的跡有3條。

3、給定圖G如下圖求：a)給出G的鄰接矩陣

b)求各結(jié)點(diǎn)的出、入度

c)求從結(jié)點(diǎn)c動(dòng)身長(zhǎng)度為3的所有回路

A(G

)=010110111100

1000

解:鄰接矩陣如圖：(按字母順序)

M（G）＝00100

10100

00011

00110

01000

a的出度是1，入度為1

b的出度是1，入度為1

c的出度是2，入度為3

d的出度是2，入度為2

e的出度是1，入度為1

曉津補(bǔ)充一下：出度就能夠數(shù)該行的非零個(gè)數(shù)，入度則可數(shù)該列的非

零個(gè)數(shù)

從結(jié)點(diǎn)c動(dòng)身長(zhǎng)度為3的回路有：c-e-b-c,c-d-d-c

4、給定G如圖所示，

a)寫(xiě)出鄰接矩陣

b)G中長(zhǎng)度為4的路有幾條？

c)G中有幾條回路？

解：(曉津有疑咨詢，v2、v3間沒(méi)有箭頭，則此圖有錯(cuò)，暫且明白為雙向連通吧)

a)M（G）＝00001

10100

01001

10100

01010

b)有52條

c)無(wú)數(shù)條

(看到這個(gè)地方，曉津認(rèn)為v2、v3間的箭頭應(yīng)向右更符合其本意，因?yàn)閳D中有某種對(duì)應(yīng)的關(guān)系。)

5、試用矩陣法推斷有向圖。

G=,}連通性。

答：別連通

曉津補(bǔ)充一下：原矩陣為：

M(G)=1001000001010000

由此矩陣得到的路徑矩陣為：

M4(G)=1001000001010000

能夠發(fā)覺(jué)圖中些結(jié)點(diǎn)間沒(méi)有路徑存在。

6、求出下圖所示圖G的鄰接矩陣、可達(dá)矩陣，找出從v2到v3長(zhǎng)度為3的初級(jí)路，并計(jì)算出A2,A3舉行驗(yàn)證。

解：鄰接矩陣為：

M(G)=0101001101010100

其余答案略，用阮同學(xué)的話講算是："太煩惱了，自個(gè)兒算一算吧":)

7、設(shè)圖G中的邊滿腳W(G-e)>W(G),稱為e為G的割邊（橋）。

證明：e是割邊，當(dāng)且僅當(dāng)e別包含在G的任一回路中。

證明：

必要性：設(shè)e是G某一連通分支的一條邊。

假設(shè)e包含在G的某一回路中，若把e去掉