浙江理工大學本科生課程離散數(shù)學-圖

圖離散數(shù)學答案浙江理工大學本科生課程計算機科學與技術(shù)系6.19無向圖如圖6.51所示

(1)G中最少的圈長為幾？最短的圈長為幾？

(2)G中最長的簡單回路長度為幾？最短的簡單回路長度為幾？

(3)求出圖的△、δ、k、λ解:(1)最長為4,v1v2v3v6v1

最短為1v1v1

(2)最長為10e1e2e3e4e5e6e7e8e9e10

最短為1e1

(3)G的最小度δ=3（v4,v5)

G的最大度△=4（v1,v2,v9,v6)

G的點連通度k=1

（割點v3)

G的邊連通度λ=2(邊割集{e2,e10},{e5,e9}等)6.19e2e5e6e4e3e1e9e8e7e11v2e10v3v4v6v5v16.206.20有向圖D如圖6.52所示

(1)D中有多少條非同構(gòu)的初級回路圈？有多少條非同構(gòu)的簡單回路？

(2)求a到d的短程線路和距離

(3)求d到a的短程線路和距離

(4)D是哪類連通圖？解:(1)初級回路（圈）c1,c2,c1≌c2,當且僅當c1與c2長度相等。有3條初級回路非同構(gòu)，長度分別為1,2,3.

非同構(gòu)的簡單回路非同構(gòu)，除以上3條，還有1條

若在定義意義下，不同起始點的回路看成不同，初級回路6條，簡單回路6+4=10條abced6.20(2)D中a到d的短程線是唯一的，即為aed,d<a,d>=2

(3)D中d到a的短程線是唯一的，即為deba,d<d,a>=3

(4)D中存在經(jīng)過每個頂點至少一次的通路，如aedbc

所以是單向連通圖，但沒有經(jīng)過每個頂點至少一次的回路，所以D不是強連通圖。

6.316.31今有甲、乙、丙三人去完成任務(wù)a,b,c,已知甲能勝任a,b,c;乙能勝任a,b;丙能勝任b,c,做三部圖G=(v1,v2,E),

其中v1={甲、乙、丙},v2={a,b,c},E={(u,v)|u∈v1,v∈v2}，并且u能勝任v},請畫出G的圖形，并且根據(jù)圖形給盡量多的分配任務(wù)方案，使得每個人去完成自己能勝任的任務(wù)。解：方案1：甲完成a,乙完成b,丙完成c

方案2：甲完成b,乙完成a,丙完成c

方案3：甲完成c,乙完成a,丙完成b

6.406.40若工廠生產(chǎn)由6種不同顏色的紗織成的雙色布，已知在品種中，每種顏色至少分別和其他5種顏色中的3種相搭配，證明可以排出3中雙色布，他們至少有6種不同的顏色。解：將有關(guān)事物之間的關(guān)系轉(zhuǎn)化成無向圖，證明所得圖為哈密頓圖。

無向簡單圖G=(V,E),其中：

V={v|v為6種顏色的紗之一}，則|V|=6

E={（u,v)|u,v∈V,且u≠v,且u與v能搭配}

由已知條件可知，u,v∈V，都有

d(u)+d(v)≥3+3=6由定理可知，存在哈密頓回路，設(shè)c=Vi1….Vi6Vi1為其中一條，由G的構(gòu)造可知，C上任何兩個頂點當且僅當它們代表的顏色的紗能織成雙色布。

比如Vi1和Vi2合，Vi3和Vi4合，Vi5和Vi6分別織成符合要求的三種雙色布，并用上6種不同的顏色。6.456.45已知7階連通平面圖G中有6個面，試求G的邊數(shù)m解：由于G為連通平面圖，有歐拉公式n–m+r=2

所以m=n+r-2=7+6-2=116