图论习题参考答案（二）
下面关于图的存储的叙述中正确的是()。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
B.用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关
C.用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数无关
D.用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
图论部分习题参考答案(二)8.2 路径与回路第5题证明：(1) 设w为分图个数。由公式m(n-w)(n-w+1)/2可得，w=3时，m(6-3)(6-3+1)/2。所以分图个数w2时，边数不能超过6条。今有7条边，所以分图个数不能超过2。(2). 任意由一个孤立顶点和一个Kn-1组成的图都满足条件。第12题解：强分图集为：v1，v2，v3，v4，v5，v6，v7，v8，v9，v10。弱分图集：v1，v2，v3，v4，v5，v6，v7，v8，v9，v10。单向分图集：v1，v2，v3，v4，v5，v6，v7，v8，v9，v10。第13题解答参见课件。第16题解答参见课件。第18题解：(a)图中a到z的最短路径为8。(b)图中a到z的最短路径为14。解答过程略，不清楚的个别解答。第19题解：(a)图的欧拉路径为：v1，v2，v3，v4，v6，v5，v3，v6，v7，v2，v8，v7，v1，v8。(b)图的欧拉回路为：v1，v2，v3，v4，v5，v2，v6，v4，v1第29题解：(1) 根据最邻近算法，起始于a点的哈密尔顿回路为：acbdea。(2) 起始于d点的哈密尔顿回路为：deacbd。(3) 最短的哈密尔顿回路为：adebca。解答过程不清楚的，个别解答。8.3 图的矩阵表示第1题解：(1).图的邻接矩阵为：(2).，由此可知，从v1到v4长度为1,2,3和4的路径分别为1,1,2,3条。(3). ，由于AAT中第（2,3）个元素为1，说明从v2和v3引出的边能共同终止于同一个结点的只有一个，即v4。AAT中第（2,2）个元素为2，说明v2的引出次数为2。由于ATA中第（2,3）个元素为0，说明没有结点引出的边同时终止于v2和v3。ATA中第（2,2）个元素为3，说明v2的引入次数为3。(4).，(5).，所以强分图的顶点集为：v1，v2，v3，v4第3题解：该图的邻接矩阵为：可达矩阵为：，8.5 二部图第1题解：图a，图b是二部图，图c不是二部图。第4题：解：由题构造一个二部图G=，其中X=P1，P2，P3，P4,.，P10。Y=a1，a2，3，.，10，表示合格工作岗位的关系，图略。可求一个最大匹配：M（P1，9），（P2，2），（P3，6），（P4，3），（P5，4），（P6，1），（P7，5）根据该匹配分配工作能使无工作的人最少。
用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边数是否相关？
正确答案:用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。
用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。
正确答案:正确
在顶点个数为n的无向图G中，若对于任意一对顶点都存在邻接关系，则无向图G共有（）条边。
正确答案:n(n-1)/2
用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边数是否相关？
正确答案:用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
正确答案:正确