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

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

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

3、；（3）；（4）（5）；（6）；（7）；（8）解答：（1）構(gòu)成通路，且為初級通路，因為點(diǎn)不重復(fù)（2）構(gòu)成了回路，但是不為簡單回路和初級回路，因為有重復(fù)的邊（3）構(gòu)成了初級通路，因為點(diǎn)不重復(fù)；（4）不構(gòu)成通路，因為邊不存在；（5）構(gòu)成通路，但是不為簡單通路和初級通路，因為有重復(fù)的邊（6）構(gòu)成了回路，但是不為簡單回路和初級回路，因為有重復(fù)的邊（7）構(gòu)成了初級通路；（8）簡單通路，但是不為初級通路，有重復(fù)邊。23、用dijkstra標(biāo)號法求圖9.22中各圖從頂點(diǎn)到其余各點(diǎn)的最短路徑和距離。解答步驟1234567到最短路為，路長為6；到最短路為，路長為3；到最短路為，路長為5；到最短路為，路長為6；到

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

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

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

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