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

本文格式為Word版，下載可任意編輯——離散數(shù)學(xué)及其應(yīng)用圖論部分課后習(xí)題答案作業(yè)答案：圖論部分

P165:習(xí)題九

1、給定下面4個圖（前兩個為無向圖，后兩個為有向圖）的集合表示，畫出它們的圖形表

示。

（1）G1??V1,E1?，V1?{v1,v2,v3,v4,v5}，E1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)}（2）G2??V2,E2?，V2?V1，E1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)}（3）D1??V3,E3?,V3?V1,E3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v1?}（4）D2??V4,E4?,V4?V1,E3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v3?}解答：（1）

（2）

10、是否存在具有以下頂點度數(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ù)個奇度頂點

。

14、設(shè)G是n(n?2)階無向簡單圖，G是它的補圖，已知?(G)?k1,?(G)?k2，求?(G)，

?(G)。

解答：?(G)?n?1?k2；?(G)?n?1?k1。

15、圖9.19中各對圖是否同構(gòu)？若同構(gòu)，則給出它們頂點之間的雙射函數(shù)。

解答：

（c）不是同構(gòu)，從點度既可以看出，一個點度序列為4，3，3，3，3而另外一個為4，4，3，3，1

（d）同構(gòu)，同構(gòu)函數(shù)為

?1?2??f(x)??3?4???5解答：

（1）三條邊一共提供6度；所以點度序列可能是

x?ax?bx?cx?dx?e16、畫出所有3條邊的5階簡單無向圖和3條邊的3階簡單無向圖。

①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度，所以點度序列可能為①3，3，0；②3，2，1；③2，2，2由于是簡單圖，①②兩種情形不可能

21、在圖9.20中，下述頂點序列是否構(gòu)成通路？哪些是簡單通路？哪些是初級通路？哪些是回路？哪些是簡單回路？哪些是初級回路？

（1）a,b,c,d,b,e；（2）a,b,e,d,b,a；（3）a,d,c,e,b；（4）d,b,a,c,e;

（5）a,b,c,d,e,b,d,c；（6）a,d,b,e,c,b,d；（7）c,d,a,b,c；（8）a,b,c,e,b解答：（1）構(gòu)成通路，且為初級通路，由于點不重復(fù)

（2）構(gòu)成了回路，但是不為簡單回路和初級回路，由于有重復(fù)的邊(a,b)（3）構(gòu)成了初級通路，由于點不重復(fù)；（4）不構(gòu)成通路，由于邊(a,c)不存在；

（5）構(gòu)成通路，但是不為簡單通路和初級通路，由于有重復(fù)的邊(d,c)（6）構(gòu)成了回路，但是不為簡單回路和初級回路，由于有重復(fù)的邊(d,b)（7）構(gòu)成了初級通路；

（8）簡單通路，但是不為初級通路，有重復(fù)邊。

23、用Dijkstra標號法求圖9.22中各圖從頂點v1到其余各點的最短路徑和距離。

解答步驟1234567v1v2v3v4v5v6v7v8(v1,0)*(v1,6)(v1,3)*(v1,?)(v1,?)(v1,?)(v1,?)(v1,?)(v1,6)(v3,5)*(v3,8)(v1,?)(v1,?)(v3,11)(v1,?)(v3,11)(v4,11)(v3,11)(v4,11)(v1,6)*(v4,6)(v4,6)*(v2,12)(v2,12)(v2,12)(v5,7)*(v4,11)(v7,10)*(v2,12)*v1到v2最短路為v1?v2，路長為6；v1到v3最短路為v1?v3，路長為3；v1到v4最短路為v1?v3?v4，路長為5；

v1到v5最短路為v1?v3?v4?v5，路長為6；v1到v6最短路為v1?v2?v6，路長為12；

v1到v7最短路為v1?v3?v4?v5?v7，路長為7；v1到v8最短路為v1?v3?v4?v5?v7?v8，路長為10；

（2）略。

25、圖9.23中各圖有幾個連通分支？給出它們所有的連通分支。

解答：

（a）有兩個連通分支：aec和bdf；（b）有三個連通分支：abd、c和ef；（c）連通圖，只有一個連通分支；（d）兩個連通分支：afbgd和ech。