第五章习题参考答案

第五章习题参考答案基础习题1（a）为多重图，平行边的重数分别为2和3。（b）为多重图，平行边的重数分别为2和3。（c）为线图，也为简单图。（d）为线图，但不是简单图。2图5-30的补图分别为（b）（c）（d）3（b）为K5的子图、真子图、为由v1,v2,v3,（c）为K5的子图、真子图、为由v1,v2,v3,（d）为K5的子图、真子图、为由v1,v2,v3,4G=（V，E）=（v1,<v5（2）（3）（4）6（1）由握手定理知，该图有16个结点。设该图有a个结点，由握手定理知，2×4+2×3+2×(a-2-2)=10×2，解得a=7设该图有a个结点，由握手定理知，2×4+1×6+2×(a-2-1)=10×2，解得a=6设该图有a个结点，每个结点的度数为b，ab=24×2，解得a=2；a=3；a=4；a=6；a=8；a=12；a=24。7（1）（2）（3）（5）能构成无向图的度数序列。（2）（3）能构成无向简单图的度数序列。8由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边数。图G的入度序列能成为2,2,2,2。9由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边数。图G的入度序列不能成为1,1,1,1。10图5-7(a)的邻接矩阵为A5图5-8(a)的邻接矩阵为A图5-9(a)的邻接矩阵为A11图5-7(a)的关联矩阵为M图5-8(a)的关联矩阵为M图5-9(a)的关联矩阵为M12图5-8(a)的邻接矩阵为A=0011长度为3的回路数为A3的对角线元素之和313图5-9(a)的邻接矩阵为A=0长度为2的回路数为A2的对角线元素之和1+3+2+2=814K4的所有非同构的子图如下，其中8-18是生成子图，3、6、7、11、12、13、14、16、17是连通图。1516提升习题1设无向图G有12条边，G中度数为3的结点有6个，其余结点的度数均小于或等于3，问G中至少有多少个结点？为什么？答：由握手定理知，G中各结点度数之和为24，6个3度结点占去18度，若其余全是3度结点，还需要2个结点，所以至少有6+2=8个结点。23阶有向完全图的所有非同构子图如下图所示，其中5-20是生成子图。

3图5-29(a)的邻接矩阵为A2−29(a)=0a13(2)=5,所以从结点v1到结点a33(2)=9,所以从结点v3到自身所有长度为2的通路数为A24图5-25b的邻接矩阵为B3=所以从v1到v1是可达的，从v2到v1、v2、v3是可达的，从v3到v3是可达的，从v4到v1、v3、v4是可达的，从vdv2,dv1,vd5v1v2v3v4v5v123456789100(无)0(无)|v1∗6(v1)3(v1)2(v1)∞(v16(v1)3(v1)2(v1)|v4∗8(v45(v3)3(v1)|v3∗8(v4)5(v3)|v2∗6(v2)12(v4)6(v2)|v5∗12(v12(v4)8(v5)|v711(v8)9(v511(v8)|11(v7到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为6v1v2v3v1234560(无)0(无)|v1∗3(v1)9(v1)3(v1)|v2∗5(v5(v2)4(v2)|v