第七章習(xí)題答案 - 副本

1、. 分析并回答下列問題： 圖中頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系? 有向圖中頂點(diǎn)的入度之和與出度之和的關(guān)系? 具有n個(gè)頂點(diǎn)的無向圖，至少應(yīng)有多少條邊才能確保是一個(gè)連通圖? 若采用鄰接矩陣表示，則該矩陣的大小是多少? 具有n個(gè)頂點(diǎn)的有向圖，至少應(yīng)有多少條弧才能確保是強(qiáng)連通圖的? 為什么? 在一個(gè)圖中, 所有頂點(diǎn)的度數(shù)之后等于所有邊數(shù)的2倍無向圖中，頂點(diǎn)的度數(shù)之和是邊數(shù)的兩倍。有向圖中，任意一條邊ab（a-b）都會(huì)給a提供一個(gè)出度，給b提供一個(gè)入度，所以頂點(diǎn)的度之和 = 2 * 頂點(diǎn)入度之和 = 2*頂點(diǎn)出度之和 = 頂點(diǎn)入度之和+頂點(diǎn)出度之和=邊數(shù)的兩倍。對任意有向圖頂點(diǎn)出度之和等于入度之和，且等于邊

2、的條數(shù)至少應(yīng)有n-1條邊。大小是n*n n 。在有向圖g中，如果對于任何兩個(gè)不相同的點(diǎn)a,b，從a到b和從b到a都存在路徑，則稱g是強(qiáng)連通圖，強(qiáng)連通圖必須從任何一點(diǎn)出發(fā)都可以回到原處,每個(gè)節(jié)點(diǎn)至少要一條出路。 設(shè)一有向圖g=(v,e)，其中v=a,b,c,d,e ， e=, , , , , , , 請畫出該有向圖，并求各頂點(diǎn)的入度和出度。 分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。有向圖：a ：出度2，入度2 b ：出度1，入度3 c ：出度2，入度1d ：出度1，入度2 e ：出度3，入度1精品.正鄰接鏈表逆鄰接鏈表 對圖7-27所示的帶權(quán)無向圖。 寫出相應(yīng)的鄰接矩陣表示。 寫出相應(yīng)的邊表表示

3、。 求出各頂點(diǎn)的度。鄰接矩陣： 9 6 3 9 5 8 6 2 9 53 5 2 7 8 9 4 5 7 4 邊表表示：精品.各頂點(diǎn)的度：頂點(diǎn)1的度：3 頂點(diǎn)2的度：3 頂點(diǎn)3的度：4頂點(diǎn)4的度：4 頂點(diǎn)5的度：3 頂點(diǎn)6的度：3 已知有向圖的逆鄰接鏈表如圖7-28所示。 畫出該有向圖。 寫出相應(yīng)的鄰接矩陣表示。 寫出從頂點(diǎn)v1開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。 畫出從頂點(diǎn)v1開始的深度優(yōu)先和廣度優(yōu)先生成樹。有向圖：精品.鄰接矩陣表示：0 1 0 1 01 0 0 0 01 1 0 0 11 0 1 0 00 1 1 1 0深度優(yōu)先遍歷序列：v1 v4 v3 v5 v2廣度優(yōu)先遍歷序列：v1 v2 v4 v3 v5或v1 v4