離散數學第九章圖的道路與連通習題答案ppt課件

1、習題十習題十 1設設G是一個是一個(n,m)簡單圖，證明：簡單圖，證明：m Cn2,等等號成立當且僅當號成立當且僅當G是完全圖。是完全圖。證明：證明：已知已知G是簡單圖，每對結點間最多一條邊，故是簡單圖，每對結點間最多一條邊，故m Cn2 。其次，當其次，當G是完全圖時，每對結點間都有一條是完全圖時，每對結點間都有一條邊，即邊，即m =Cn2 , 反之亦然。反之亦然。證明：在不少于證明：在不少于2人的一群人中，至少有人的一群人中，至少有2個人這群人中有相個人這群人中有相同數目的朋友。同數目的朋友。證明：證明：可轉化為圖論問題，以人為結點，如果可轉化為圖論問題，以人為結點，如果2人是朋友關系，就

2、人是朋友關系，就對應的對應的2個結點之間連一條邊。個結點之間連一條邊。問題轉化為求簡單圖問題轉化為求簡單圖G中有至少中有至少2個結點度相同。個結點度相同。如果不是如此，如果不是如此，n個結點的度只能在個結點的度只能在0,1,2,n-1中取值，但中取值，但0度和度和n-1度不能共存，因此，要么是度不能共存，因此，要么是0,1,2,n-2，要么是，要么是1,2,n-1。據抽屜原理，必有至少。據抽屜原理，必有至少2個結點的度相同。個結點的度相同。證明：證明： 在在(n,m)圖中，圖中， 2m/n 證明：證明：對任何對任何v V， d(v) , d(v) , 即即 n 2m n ，即即 2m/n 習題

3、十習題十 4習題十習題十 6設設G是是(n,m)簡單二部圖，證明：簡單二部圖，證明： m n2/4證明：證明：這個二部圖兩部結點數分別設為這個二部圖兩部結點數分別設為k和和n-k, 其邊數其邊數m (n-k)k n2/4若若G G，稱，稱G是自補圖。確定一個圖為自補圖的最是自補圖。確定一個圖為自補圖的最低條件；畫出一個自補圖來。低條件；畫出一個自補圖來。解：解：若若G G，n階圖階圖G的邊數應為的邊數應為Kn邊數的一半，即邊數的一半，即m=n(n-1)/4,一個圖為自補圖的最低條件可設為結一個圖為自補圖的最低條件可設為結點數須為點數須為4k或或4k+1。例如：當例如：當k=1時：時：習題十習題

4、十 9判別圖中兩圖是否同構，并說明理由。判別圖中兩圖是否同構，并說明理由。解：解：兩圖不同構。因為如果同構，兩圖中唯一的兩圖不同構。因為如果同構，兩圖中唯一的3度結點度結點應對應，但左圖應對應，但左圖3度點的鄰接結點度數分布是度點的鄰接結點度數分布是2，1，1，而右圖的為，而右圖的為2，2，1，不對應。，不對應。習題十習題十 10若若U和和V是圖是圖G中僅有的兩個奇數度結點，證明中僅有的兩個奇數度結點，證明 U和和V必是連通的必是連通的 。證明：證明：如果如果U和和V不連通，則應各屬一支，但此時它們所在不連通，則應各屬一支，但此時它們所在支只有唯一的奇數度結點，與圖論基本定理推論支只有唯一的奇

5、數度結點，與圖論基本定理推論矛盾。矛盾。習題十習題十 15證明：證明：G是二部圖當且僅當是二部圖當且僅當G的回路都是偶長回路。的回路都是偶長回路。證明：證明：（）當）當G是二部圖時，設其二部劃分為是二部圖時，設其二部劃分為，則任何起，則任何起于于X部結點的回路應是部結點的回路應是C=x1y1x2y2 xkykx1的形式，其的形式，其長度為長度為2k，即是偶長回路。，即是偶長回路。（）當）當G的回路都是偶長回路時，設的回路都是偶長回路時，設G連通，任取定一個連通，任取定一個結點結點u，構造集合，構造集合X=x V且且x到到u的最短道路長度為偶數的最短道路長度為偶數Y=V-X首先，首先， u X，

6、所以，所以X ，其次，其次，X中無鄰接結點，否則設中無鄰接結點，否則設x1x2 E，則可得出，則可得出G中存在奇長回路，矛盾。同理可證中存在奇長回路，矛盾。同理可證Y中無鄰接結點。即中無鄰接結點。即是是G的二部劃分。的二部劃分。習題十習題十 16設設G=（V，E是點度都為偶數的連通圖，證明：是點度都為偶數的連通圖，證明：對任何對任何v V，(G-v) d(v)證明：證明：設設G-v有有k支，支，G1G2 Gk ，則每支和，則每支和v至少有至少有2邊邊相連，所以相連，所以(G-v) d(v)習題十習題十 19求出圖的鄰接矩陣、可達矩陣、強分圖和關聯(lián)矩陣。求出圖的鄰接矩陣、可達矩陣、強分圖和關聯(lián)矩

7、陣。解：解： 鄰接矩陣鄰接矩陣A= A= 可達矩陣可達矩陣P=P=P PT= P PT= 所以強分圖有：所以強分圖有：a,b,c,d,e,f,ga,b,c,d,e,f,g0 1 0 1 0 0 00 0 1 0 1 0 01 1 0 0 1 0 00 0 1 0 0 0 00 0 0 0 0 0 00 0 0 0 1 0 10 0 0 0 1 1 01 1 1 1 1 0 01 1 1 1 1 0 01 1 1 1 1 0 01 1 1 1 1 0 00 0 0 0 0 0 00 0 0 0 1 1 10 0 0 0 1 1 11 1 1 1 0 0 01 1 1 1 0 0 01 1 1 1 0 0 01 1 1 1 0 0 00 0 0 0 1 0 00 0 0 0 0 1