《离散数学第九章图的道路与连通习题答案》由会员分享，可在线阅读，更多相关《离散数学第九章图的道路与连通习题答案（10页珍藏版）》请在金锄头文库上搜索。
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-G-v) d(v)证明：证明：设设G-G-v有有k支，支，G1G2 Gk ，则每支和，则每支和v至少有至少有2边相边相连，所以连，所以( (G-G-v) d(v)习题十习题十 19求出图的邻接矩阵、可达矩阵、强分图和关联矩阵。求出图的邻接矩阵、可
7、达矩阵、强分图和关联矩阵。解：解： 邻接矩阵邻接矩阵A= A= 可达矩阵可达矩阵P=P=P PP PT T= = 所以强分图有：所以强分图有：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 10 0 0 0 0 1 1a b c d e f g a b c d e f g a b c d e f g ab c d e f g ab c d e f g ab c d e f g abcdefg习题十习题十 30
