1、1,第六章習(xí)題解答,P201: T6.12設(shè)G為n(n2)階無向簡單圖，證明：若G為自補(bǔ)圖，則n=4k或n=4k+1，其中k為正整數(shù)。,2,第六章習(xí)題解答,P201:T6.12設(shè)G為n(n2)階無向簡單圖，證明：若G為自補(bǔ)圖，則n=4k或n=4k+1，其中k為正整數(shù)。 證:(1)由補(bǔ)圖定義有 設(shè)G和 的邊數(shù)為m1和m2，則 m1+m2=n(n-1)/2 (Kn的邊數(shù)) (2)由于G為自補(bǔ)圖，所以 m1=m2,記m1=m2=m,有 m1+m2=2m=n(n-1)/2 m=n(n-1)/4,3,第六章習(xí)題解答,P201: T6.12設(shè)G為n(n2)階無向簡單圖，證明：若G為自補(bǔ)圖，則n=4k或n=

2、4k+1，其中k為正整數(shù)。 證: m=n(n-1)/4 (3)由于n和n-1是連續(xù)的自然數(shù)，一奇一偶，又因m是整數(shù)，必有以下兩種情況： 情況1:n=4k 情況2:n-1=4k n=4k+1,4,第六章習(xí)題解答,P201: T6.19設(shè)無向圖G如圖6.51所示, (1)G中最短的圈長為幾?最長的圈長為幾? (2)G中最短的簡單回路長度為幾?最長的簡單回路長度為幾? (3)求出G中的.,5,第六章習(xí)題解答,P201: T6.19設(shè)無向圖G如圖6.51所示, (1)G中最短的圈長為幾?最長的圈長為幾? (2)G中最短的簡單回路長度為幾?最長的簡單回路長度為幾? (3)求出G中的, ,. 解:(1)G

3、中最短的圈長為1;最長的圈長為4 (2)G中最短的簡單回路長度為1;最長的簡單回路長度為10 (3) =3,=4 =1(有割點(diǎn)). (最小的邊割集有兩條邊),6,T6.24 (1) v1到v4, 長度為1,2,3,4的通路各有多少條? (2) v1到v4長度小于等于3的通路各有多少條? (3) v1到自身長度為1,2,3,4的回路各有多少條? (4) v4到自身長度小于等于3的回路各有多少條? (5) 長為4的通路共有多少條（不含回路）? (6) 長度等于4的回路共有多少條? (7) 長度小于等于4的通路共有多少條?其中回路共有多少條? (8) 寫出D的可達(dá)矩陣, 并問D是強(qiáng)連通的嗎? 解,v

4、1,v2,v3,v4,7,(1) v1到v4, 長度為1,2,3,4的通路各有0,0,2,2條 (2) v1到v4長度小于等于3的通路各有2條 (3) v1到自身長度為1,2,3,4的回路各有1,1,3,5條 (4) v1到自身長度小于等于3的回路各有5條 (5) 長為4的通路共有33條（不含回路） (6) 長度等于4的回路共有11條 (7) 長度小于等于4的通路共有88條?其中回路共有22條,8,所有都連通，D是連通圖，可達(dá)矩陣全,3,可達(dá)矩陣,9,第六章習(xí)題解答,P202: T6.31今有甲乙丙人去完成任務(wù)a,b,c,已知甲能勝任a,b,c，乙能勝任a,b，丙能勝任b,c， 做二部圖G= ,其中V1=甲,乙,丙, V2=a,b,c,E=(u,v)|uV1, vV2,u能勝任v 請(qǐng)畫出的圖形，并且