图论及其应用1-3章习题答案

习题一1. （题 14）：证明图 1-28 中的两图是同构的证明 将图 1-28 的两图顶点标号为如下的(a)与(b)图作映射 f : f(vi)ui (1 i  10)容 易 证 明 ， 对  vivjE((a)), 有 f(vivj)uiujE((b)) (1 i  10, 1j 10 )由图的同构定义知，图 1-27 的两个图是同构的。2. （题 6）设 G 是具有 m 条边的 n 阶简单图。证明：m =当且仅当 G 是完全图。证明 必要性 若 G 为非完全图，则 vV(G),有 d(v) n-1   d(v)  n(n-1)  2mn(n-1) m  n(n-1)/2=, 与已知矛盾！图 1-28 充分性 若 G 为完全图，则 2m= d(v) =n(n-1)  m= 。3. （题 9）证明：若 k 正则偶图具有二分类 V= V1∪V2，则 | V1| = |V2|。 证明 由于 G 为 k 正则偶图，所以，k V1  =m = k V2   V1= V2 。4. （题 12）证明：若 δ≥2，则 G 包含圈。证明 只就连通图证明即可。设 V(G)=｛v1,v2,…,vn｝,对于 G 中的路 v1v2…vk,若 vk与 v1邻接，则构成一个圈。若 vi1vi2…vin是一条路，由于 2，因此，对 vin，存在点 vik与之邻接，则 vikvinvik构成一个圈 。 5. （题 17）证明：若 G 不连通，则连通。证明 对,若 u 与 v 属于 G 的不同连通分支，显然 u 与 v 在中连通；若 u 与 v 属于 g 的同一连通分支，设 w 为 G 的另一个连通分支中的一个顶点，则 u 与 w，v 与 w 分别在中连通，因此，u 与 v 在中连通。习题二2、证明：每棵恰有两个 1 度顶点的树均是路。 证明：设树 T 为任意一个恰有两个 1 度顶点的树，则 T 是连通的，且无圈，令 V1、V2 为度为 1 的顶点，由于其他的顶点度数均为 0 或者 2，且 T 中无圈，则从 V1到 V2 有且只有一条连通路。所以，每棵恰有两个 1 度顶点的树均是路。得证。5、证明：正整数序列是一棵树的度序列当且仅当。 证明：设正整数序列是一棵树 T 的度序列，则满足，E 为 T 的边数，又有边数和顶点的关系，所以14、证明：若 e 是的边，则。若 e 为 Kn 的一条边，由 Kn 中的边的对称性以及每棵生成树的边数为 n-1，Kn 的所有生 成 树 的 总 边 数 为 ：， 所 以 ， 每 条 边 所 对 应 的 生 成 树 的 棵 数 为 ：，所以，K n - e 对应的生成树的棵数为：16、Kruskal 算...