(完整版)图论及其应用1-3章习题答案(电子科大).docxVIP

2 2 习题一 1.(题14):证明图1-28中的两图是同构的 图 1-28 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射 f : f(v i) ui (1 i 10) 容易证明，对 ViVj E((a)),有 f(v iVj) UiUj E((b)) (1 i 由图的同构定义知，图1-27的两个图是同构的。 2. (题6)设G是具有m条边的n阶简单图。证明: 完全图。 证明 必要性 若G为非完全图，贝U v V(G),有d(v) n-1 2m n(n-1) m n(n-1)/2= 与已知矛盾! 充分性 若G为完全图，则2m= d(v) =n(n-1) m= 10, 1 j 10 ) 当且仅当G是 d(v) n(n-1) n 。 3.(题9)证明：若k正则偶图具有二分类 V= V1U V,则| V1| = |側 证明由于G为k正则偶图，所以，k Vi =m = k V Vi = V2 。 (题12)证明：若3》2,则G包含圈。 证明 只就连通图证明即可。设 V(G)= {Vl,V2,…,v n},对于G中的路VlV2… Vk,若Vk与Vi邻接，则构成一个圈。若Vi1 Vi2…Vin是一条路，由于 2,因此，对 Vin，存在点Vik与之邻接，则Vik Vin Vik构成一个圈。 (题17)证明：若G不连通，则G连通。 证明 对u,V V(G),若u与V属于G的不同连通分支，显然u与V在G中 连通；若u与V属于g的同一连通分支，设w为G的另一个连通分支中的一个顶 点，则u与w, V与w分别在G中连通，因此，u与V在G中连通。 习题二 2、证明：每棵恰有两个 1度顶点的树均是路。 证明：设树T为任意一个恰有两个 1度顶点的树，则 T是连通的，且无圈，令 Vi 、V2为度为1的顶点，由于其他的顶点度数均为 0或者2,且T中无圈，则从 V1到V2有 且只有一条连通路。所以，每棵恰有两个 1度顶点的树均是路。得证。 n 5、证明：正整数序列(d1,d2,…,dn)是一棵树的度序列当且仅当 di 2(n 1)。 i 1 n 证明：设正整数序列(d1,d2,…，dn)是一棵树T的度序列，则满足 di 2E，E为T i 1 n 的边数，又有边数和顶点的关系 n E 1，所以 di 2(n 1) i 1 14、证明：若e是Kn的边，则(Kn e) (n 2)nn 3。 若e为Kn的一条边，由Kn中的边的对称性以及每棵生成树的边数为 n-1，Kn的所有 (n 1)nn^n(n 1)生成树的总边数为：(n 1)n (n 1)nn ^n(n 1) 2nn 3,所以，K n - e对应的生成树的棵数为: (Kn e) nn 2 2nn3 (n 2)nn 3 16、Kruskal算法能否用来求： 赋权连通图中的最大权值的树？ 赋权图中的最小权的最大森林？如果可以，怎样实现? 解：(1)不能，Kruskal算法得到的任何生成树一定是最小生成树。 (2)可以，步骤如下： 步骤一：选择边el,是的 尽可能小； 步骤二：若已选定边ei,e2,...,e，则从E {e，e2,…e}选取ei 1，使 a、 G[{e,e2,...ej 为无圈图 b、 (e J是满足a的尽可能小的权； 步骤三：当步骤二不能继续执行时停止； 习题二 3.设G是阶大于2的连通图，证明下列命题等价： G是块 G无环且任意一个点和任意一条边都位于同一个圈上； G无环且任意三个不同点都位于同一条路上。 证明：(1 )t( 2)： 错误!未找到引用源。 是块，任取 错误!未找到引用源。 的一点错误!未找到引用源。， 一边错误!未找到引用源。，在错误！未找到引用源。 边插入一点错误！未找到引用源。， 使得错误!未找到引用源。 成为两条边，由此得到新图 Gl，显然错误!未找到引用源。 的是阶数大于3的块，由定理，错误!未找到引用源。中的u,v位于同一个圈上，于是 错误!未找到引用源。 中u与边错误!未找到引用源。 都位于同一个圈上。 (2)宀⑶： 〕无环，且任意一点和任意一条边都位于同一个圈上，任取 错误!未找到引用源。的 点u,边e,若错误!未找到引用源。 在错误!未找到引用源。 上，则三个不同点位于同一个 闭路，即位于同一条路，如 错误!未找到引用源。 不在错误!未找到引用源。 上，由定理， 错误!未找到引用源。的两点在同一个闭路上，在 错误!未找到引用源。 边插入一个点v,由 此得到新图错误!未找到引用源。，显然错误!未找到引用源。的是阶数大于3的块，则两条 边的三个不同点在同一条路上。 (3)宀⑴： 错误！未找到引用源。连通，若错误！未找到引用源。不是块，则错误！未找到引用源。 中存在着割点错误!未找到引用源。，划分为不同的子集块 错误!未找到引用源。，错误！ 未找到引用源。