離散數(shù)學(xué)及其應(yīng)用圖論部分課后習(xí)題答案

1、作業(yè)答案：圖論部分p165:習(xí)題九1、 給定下面4個(gè)圖（前兩個(gè)為無(wú)向圖，后兩個(gè)為有向圖）的集合表示，畫出它們的圖形表示。（1），（2），（3）（4）解答：（1）（2）10、是否存在具有下列頂點(diǎn)度數(shù)的5階圖？若有，則畫出一個(gè)這樣的圖。（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4解答：（1）（3）不存在，因?yàn)橛衅鏀?shù)個(gè)奇度頂點(diǎn)。14、設(shè)g是階無(wú)向簡(jiǎn)單圖，是它的補(bǔ)圖，已知，求，。解答：；。15、圖9.19中各對(duì)圖是否同構(gòu)？若同構(gòu)，則給出它們頂點(diǎn)之間的雙射函數(shù)。解答：（c）不是同構(gòu)，從點(diǎn)度既可以看出，一個(gè)點(diǎn)度序列為4，3，3，3，3而另外一個(gè)為4

2、，4，3，3，1（d）同構(gòu)，同構(gòu)函數(shù)為16、畫出所有3條邊的5階簡(jiǎn)單無(wú)向圖和3條邊的3階簡(jiǎn)單無(wú)向圖。解答：（1）三條邊一共提供6度；所以點(diǎn)度序列可能是3，3，0，0，0，0；3，2，1，0，0，0；3，1，1，1，0，0；2，2，2，0，0，0；2，2，1，1，0，0；2，1，1，1，1，0；1，1，1，1，1，1；由于是簡(jiǎn)單圖，兩種情形不可能圖形如下：（2）三條邊一共提供6度，所以點(diǎn)度序列可能為3，3，0；3，2，1；2，2，2由于是簡(jiǎn)單圖，兩種情形不可能21、在圖9.20中，下述頂點(diǎn)序列是否構(gòu)成通路？哪些是簡(jiǎn)單通路？哪些是初級(jí)通路？哪些是回路？哪些是簡(jiǎn)單回路？哪些是初級(jí)回路？（1）；（2）

3、；（3）；（4）（5）；（6）；（7）；（8）解答：（1）構(gòu)成通路，且為初級(jí)通路，因?yàn)辄c(diǎn)不重復(fù)（2）構(gòu)成了回路，但是不為簡(jiǎn)單回路和初級(jí)回路，因?yàn)橛兄貜?fù)的邊（3）構(gòu)成了初級(jí)通路，因?yàn)辄c(diǎn)不重復(fù)；（4）不構(gòu)成通路，因?yàn)檫叢淮嬖?；?）構(gòu)成通路，但是不為簡(jiǎn)單通路和初級(jí)通路，因?yàn)橛兄貜?fù)的邊（6）構(gòu)成了回路，但是不為簡(jiǎn)單回路和初級(jí)回路，因?yàn)橛兄貜?fù)的邊（7）構(gòu)成了初級(jí)通路；（8）簡(jiǎn)單通路，但是不為初級(jí)通路，有重復(fù)邊。23、用dijkstra標(biāo)號(hào)法求圖9.22中各圖從頂點(diǎn)到其余各點(diǎn)的最短路徑和距離。解答步驟1234567到最短路為，路長(zhǎng)為6；到最短路為，路長(zhǎng)為3；到最短路為，路長(zhǎng)為5；到最短路為，路長(zhǎng)為6；到

4、最短路為，路長(zhǎng)為12；到最短路為，路長(zhǎng)為7；到最短路為，路長(zhǎng)為10；（2）略。25、圖9.23中各圖有幾個(gè)連通分支？給出它們所有的連通分支。解答：（a）有兩個(gè)連通分支：和；（b）有三個(gè)連通分支：、和；（c）連通圖，只有一個(gè)連通分支；（d）兩個(gè)連通分支：和。38、寫出圖9.27的關(guān)聯(lián)矩陣。解答：40、寫出圖9.29中各圖的鄰接矩陣。解答：(a); (b)41、設(shè)有向圖，其中，其鄰接矩陣為試求出中各頂點(diǎn)的入度和出度。解答：出度： 入度：43、有向圖d如圖9.29（a）所示（1）d中道長(zhǎng)度為1，2，3，4的通路各有幾條？（2）d中道長(zhǎng)度為1，2，3，4的通路各有幾條？（3）d中長(zhǎng)度為4的通路有多少條

5、？其中長(zhǎng)為4的回路有多少條？（4）d中長(zhǎng)度小于或者等于4的通路有多少條？其中多少條為回路？（5）寫出d的可達(dá)矩陣。解答：，則，（1）d中道長(zhǎng)度為1，2，3，4的通路各有0，0，2，2條；（2）d中道長(zhǎng)度為1，2，3，4的通路各有1，1，3，5條；（3）d中長(zhǎng)度為4的通路有44條；其中長(zhǎng)為4的回路有11條.（4）d中長(zhǎng)度小于或者等于4的通路有88條；其中22條為回路。（5）寫出d的可達(dá)矩陣為。p181:習(xí)題十1、 圖10.14中的哪些圖是樹？解答：（a）是樹；（b）不是樹，因?yàn)椴贿B通。3、無(wú)向樹t有8片樹葉，2個(gè)3度分支點(diǎn)，其余分支點(diǎn)都是4度頂點(diǎn)，問t有幾個(gè)4度分支點(diǎn)？請(qǐng)畫出3棵非同構(gòu)的這種無(wú)向

6、樹。解答：設(shè)有個(gè)4度分支點(diǎn)，則t共有個(gè)頂點(diǎn)。那么有條邊。由握手定理有所以有2個(gè)4度分支點(diǎn)。4、無(wú)向樹t有個(gè)i度分支點(diǎn)，其余頂點(diǎn)都為樹葉，問t有幾片樹葉？解答：設(shè)有片樹葉，共有個(gè)頂點(diǎn)，那么有條邊，而共有度，由握手定理可知所以有。15、已知n階m條邊的無(wú)向圖g是棵樹組成的森林。證明：。證明：方法一：對(duì)變量進(jìn)行歸納當(dāng)是，因?yàn)槭且豢脴?，顯然成立；假設(shè)n階m條邊的無(wú)向圖g是棵樹組成的森林，有；那么對(duì)于n階m條邊的無(wú)向圖g是棵樹組成的森林，在任意兩棵樹中分別找一點(diǎn)進(jìn)行連一條邊，那么得到的圖則為n階m+1條邊的無(wú)向圖g是棵樹組成的森林，那么，所以。方法二：設(shè)棵樹中，分別有個(gè)頂點(diǎn)和條邊，則有，即可得證。19、

7、求圖10.17中兩個(gè)帶權(quán)圖的最小生成樹。解答：p204:習(xí)題十一1、判斷圖11.22中哪些是歐拉圖？哪些是半歐拉圖？對(duì)歐拉圖給出一條歐拉回路。對(duì)半歐拉圖給出一條歐拉通路。對(duì)不是的，說(shuō)明不是歐拉圖或半歐拉圖的理由。解答：（a）為歐拉圖，全為偶度頂點(diǎn)；（b）為半歐拉圖，1，2兩個(gè)頂點(diǎn)點(diǎn)度為3，其它為偶數(shù)。2、判斷圖11.23中哪些是歐拉圖？哪些是半歐拉圖？對(duì)歐拉圖給出一條歐拉回路。對(duì)半歐拉圖給出一條歐拉通路。對(duì)不是的，說(shuō)明不是歐拉圖或半歐拉圖的理由。解答：（a）為半歐拉圖，a,c兩點(diǎn)的出度和入度都相等；b點(diǎn)的入度比出度大1；c點(diǎn)的入度比出度小1.（b）為歐拉圖，每個(gè)頂點(diǎn)的入度和出度都相等。3、判斷命題的真假。（1）完全圖是歐拉圖。（2）階有向完全圖是歐拉圖。（3）當(dāng)r,s為正偶數(shù)時(shí)，完全二部分圖是歐拉圖。解答：（1）為假，因?yàn)楫?dāng)n為偶數(shù)時(shí)，每個(gè)點(diǎn)的點(diǎn)度都為奇數(shù)。（2）真；有向完全圖的出度和入度必然相等。（3）真，完全二部分圖中，一部分點(diǎn)的點(diǎn)度全為r,另外一部分點(diǎn)的點(diǎn)度全為s。10.說(shuō)明圖11.25中各圖不是哈密頓圖，也不半哈密頓圖的理由。解答：（a）刪掉畫圈的3個(gè)頂點(diǎn)，還剩下5個(gè)連通分支；（b）刪掉畫圈的4個(gè)頂點(diǎn)，還剩下6個(gè)連通分支。由定理11.2和11.3可知不是哈密頓圖，也不半哈密頓圖。11、設(shè)g是無(wú)向連通圖，證明：若g中有橋或者割點(diǎn)，則g不是哈密頓