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

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

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

阮允準同學提供答案:

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

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

解得：x≥4

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

因此G至少有11個結(jié)點

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

阮允準同學答案：

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

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

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

由上可知，G中至少有5個6度點或至少有6個5度點。

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

阮同學以為題中應指定是無向簡單圖.

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

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

阮同學給出證明如下：

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

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

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

6、畫出所有5個結(jié)點3條邊，以及5個結(jié)點7條邊的簡單圖。

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

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

證明如下：

在兩圖中我們能夠看到有

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

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

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

阮同學給出證明如下：

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

fv,gw,hx

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

阮同學證明如下：

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

5.2習題參考答案

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

解：從A到F的初級路有：

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

2、給定圖G，如下圖所示，找到G中從v2動身的所有初級回路。

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

從V2動身的初級回路有：V2V4V1V2、V2V3V4V1V2.

3、設G為無向連通圖，有n個結(jié)點，這么G中至少有幾條邊？為啥？對有向圖怎么？

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

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

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

解：

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

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

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

6、一具有向圖是強連通的，當且僅當G中有一具回路，它至少包含每個結(jié)點一次。

證明如下：

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

充分性：當G中有一具回路，它至少包含每個結(jié)點一次時，能夠懂，任一結(jié)點可達其他所有結(jié)點，所以它是強連通的。

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

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

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

以下是阮同學的答案：

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

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

（2）若v1、v2無邊，則v1和剩下的結(jié)點中的n個結(jié)點有邊相連，v2也和剩下的結(jié)點中的n個結(jié)點有邊相連。因為剩下的結(jié)點最多惟獨2n-2個，由抽屜原理可得，至少存在一具結(jié)點，它和v1、v2都有邊相連，此刻v1和v2也是連通的。

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

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

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

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

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

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

上面的答案是錯誤的，阮允準同學糾正如下：因為一具連通圖至少要有n-1條邊，但并別是講至少有n-1條邊的圖一定是連通圖。同時容易驗證那個結(jié)論別成立。

證明如下：

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

下面我用數(shù)學歸納法進一步證明：

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

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

（3）當n=k+1時，若此刻每個結(jié)點度數(shù)為k，則結(jié)論顯然成立，否則必存在一具結(jié)點v度數(shù)至多惟獨k-1度，即那個結(jié)點最多惟獨k-1條邊和它相連。因為此刻總的邊數(shù)e>0.5k(k-1),則其它k個結(jié)點之間的邊數(shù)e'＞

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

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

5.3習題參考答案

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

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

解：1、v1的入度是3.

v4的出度是1，

因為

A2(G)=2011

22011112

0101

因此從v1到v4長度為2的路有1條。

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

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

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

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

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

c)求從結(jié)點c動身長度為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

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

零個數(shù)

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

4、給定G如圖所示，

a)寫出鄰接矩陣

b)G中長度為4的路有幾條？

c)G中有幾條回路？

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

a)M（G）＝00001

10100

01001

10100

01010

b)有52條

c)無數(shù)條

(看到這個地方，曉津認為v2、v3間的箭頭應向右更符合其本意，因為圖中有某種對應的關(guān)系。)

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

G=,}連通性。

答：別連通

曉津補充一下：原矩陣為：

M(G)=1001000001010000

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

M4(G)=1001000001010000

能夠發(fā)覺圖中些結(jié)點間沒有路徑存在。

6、求出下圖所示圖G的鄰接矩陣、可達矩陣，找出從v2到v3長度為3的初級路，并計算出A2,A3舉行驗證。

解：鄰接矩陣為：

M(G)=0101001101010100

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

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

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

證明：

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

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