习题一1. （题 14） ：证明图 1-28 中的两图是同构的证明 将图 1-28 的两图顶点标号为如下的 (a) 与(b) 图作映射 f : f(vi)ui (1 i 10) 容易证明，对vivjE(a),有 f(vivj) uiujE(b) (1i 10, 1j10 ) 由图的同构定义知，图1-27 的两个图是同构的2. （题 6）设 G是具有 m条边的 n 阶简单图证明： m =2n当且仅当 G是完全图证明 必要性 若 G为非完全图，则vV(G), 有 d(v)n-1 d(v) n(n-1) 2m n(n-1) m n(n-1)/2=2n, 与已知矛盾！充分性 若 G为完全图，则 2m= d(v) =n(n-1) m= 2n3. （题 9）证明：若 k 正则偶图具有二分类V= V1V2，则 | V1| = |V2| 图 1-28 (a) v1v2v3v4v5v6v7 v8v9v10 u1u2u3u4u5u6u7u8u9u10(b) 证明 由于 G为k正则偶图，所以， k V1 =m = k V2V1= V24. （题 12）证明：若 2，则 G包含圈证明 只就连通图证明即可设V(G)=v1,v2, ,vn, 对于 G中的路 v1v2vk, 若 vk与 v1邻接，则构成一个圈。
若vi1vi2vin是一条路，由于2，因此，对vin，存在点 vik与之邻接，则 vikvinvik构成一个圈5. （题 17）证明：若 G不连通，则G连通证明 对)(,_GVvu, 若 u 与 v 属于 G的不同连通分支，显然u 与 v 在_G 中连通；若 u 与 v 属于 g 的同一连通分支， 设 w为 G的另一个连通分支中的一个顶点，则 u 与 w，v 与 w分别在_G 中连通，因此， u 与 v 在_G 中连通习题二2、证明：每棵恰有两个1 度顶点的树均是路证明：设树T 为任意一个恰有两个1 度顶点的树，则T 是连通的，且无圈，令V1、V2 为度为 1 的顶点，由于其他的顶点度数均为0 或者 2，且 T 中无圈，则从V1到 V2 有且只有一条连通路所以，每棵恰有两个1 度顶点的树均是路5、证明：正整数序列),.,(21nddd是一棵树的度序列当且仅当)1(21ndnii证明：设正整数序列),.,(21nddd是一棵树T 的度序列，则满足Ednii21，E 为 T的边数，又有边数和顶点的关系1En，所以)1(21ndnii14、证明：若e 是nK的边，则3)2()(nnnneK若 e 为 Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1， Kn 的所有生 成 树 的 总 边 数 为 ：2)1(nnn， 所 以 ， 每 条 边 所 对 应 的 生 成 树 的 棵 数 为 ：322)1(21)1(nnnnnnn，所以， K n - e 对应的生成树的棵数为：332)2(2)(nnnnnnnneK16、 Kruskal 算法能否用来求：（1）赋权连通图中的最大权值的树？（2）赋权图中的最小权的最大森林？如果可以，怎样实现？解： （1）不能， Kruskal 算法得到的任何生成树一定是最小生成树。
2）可以，步骤如下：步骤一：选择边e1，是的)(1e尽可能小；步骤二：若已选定边ieee,.,21，则从,.,21ieeeE选取1ie，使a、,.,121ieeeG为无圈图b、)(1ie是满足 a 的尽可能小的权；步骤三：当步骤二不能继续执行时停止；习题三3. 设 G是阶大于2 的连通图，证明下列命题等价：（1）G是块（2）G无环且任意一个点和任意一条边都位于同一个圈上；（3）G无环且任意三个不同点都位于同一条路上证明： （1）（ 2） ：错误 ! 未找到引用源是块，任取 错误 ! 未找到引用源的一点 错误 ! 未找到引用源 ，一边 错误 ! 未找到引用源 ，在 错误 ! 未找到引用源边插入一点 错误 ! 未找到引用源 ，使得 错误 ! 未找到引用源成为两条边，由此得到新图1G，显然 错误 ! 未找到引用源的是阶数大于3 的块，由定理，错误 ! 未找到引用源中的 u,v 位于同一个圈上，于是错误 ! 未找到引用源中 u与边 错误 ! 未找到引用源都位于同一个圈上2) (3): 无环，且任意一点和任意一条边都位于同一个圈上，任取错误 ! 未找到引用源的点 u，边 e，若 错误 ! 未找到引用源。
在错误 ! 未找到引用源上，则三个不同点位于同一个闭路，即位于同一条路，如错误 ! 未找到引用源不在 错误 ! 未找到引用源上，由定理，错误 ! 未找到引用源的两点在同一个闭路上，在错误 ! 未找到引用源边插入一个点v，由此得到新图 错误 ! 未找到引用源 ，显然 错误 ! 未找到引用源的是阶数大于3 的块，则两条边的三个不同点在同一条路上 (3)(1): 错误 ! 未找到引用源 连通， 若错误 ! 未找到引用源 不是块， 则错误 ! 未找到引用源中存在着割点 错误 ! 未找到引用源 ，划分为不同的子集块错误 ! 未找到引用源 错误 !未找到引用源 错误 ! 未找到引用源 错误 ! 未找到引用源无环，12,xv yv，点错误 ! 未找到引用源在每一条 错误 ! 未找到引用源的路上，则与已知矛盾，错误 ! 未找到引用源13、设 H是连通图G的子图，举例说明：有可能k(H) k(G). 解：通常 错误 ! 未找到引用源 整个图为 错误 ! 未找到引用源 ，割点 错误 ! 未找到引用源左边的图错误 ! 未找到引用源为错误 ! 未找到引用源的的子图， 错误 ! 未找到引用源错误 ! 未找到引用源。
，则 错误 ! 未找到引用源 15、设 T 是简单连通图G的生成树，)(TEGT称为 G的余树，图G的极小边割是指其任何真子集均不是边割的边割证明：（1）T不含 G的极小边割2）eT包含 G的唯一的极小边割，其中e 为 G的不在T中的边证明： （1）设T含有 G的极小边割S，则 T 中不含极小边割S，由于 T 是简单连通图G的生成树， 则 T 中必然含有一组极小割边，这与 T 中不含极小割边相矛盾，则T中不含 G的极小边割2）假设 e 为T中的一条边， 根据（1）得T+e 中仍不含G的极小割边， 这与eT包含 G的唯一的极小边割相矛盾，则e 为 G的不在T中的边，得证e H 。