习题一
1. （题14）：证明图1-28中的两图是同构的 图1-28
证明 将图1-28的两图顶点标号为如下的(a)与(b)图
u1 v1
u6 u5 v6 v10 v5 v2 u2 u8 v7 u10 u3 v8 v9 u4 u u 79 v4 v3 (b) (a)
作映射f : f(vi)?ui (1? i ? 10)
容易证明，对?vivj?E((a)),有f(vivj)?uiuj?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。
?n?2. （题6）设G是具有m条边的n阶简单图。证明：m =??2??当且仅当G是
??完全图。
证明 必要性 若G为非完全图，则? v?V(G),有d(v)? n-1 ? ? d(v) ? n(n-1) ? 2m?n(n-1)
?n?? m ? n(n-1)/2=??2??, 与已知矛盾！
???n? 充分性 若G为完全图，则 2m=? d(v) =n(n-1) ? m= ??2??。
??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不连通，则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是连通的，且无圈，令V1
、V2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T中无圈，则从V1到V2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 5、证明：正整数序列(d1,d2,...,dn)是一棵树的度序列当且仅当
?di?1ni?2(n?1)。
n 证明：设正整数序列(d1,d2,...,dn)是一棵树T的度序列，则满足
n?di?1i?2E，E为T
的边数，又有边数和顶点的关系n?E?1，所以??di?1i?2(n?1)
n?314、证明：若e是Kn的边，则?(Kn?e)?(n?2)n。
若e为Kn的一条边，由Kn中的边的对称性以及每棵生成树的边数为n-1，Kn的所有生成树的总边数为：(n?1)nn?2，所以，每条边所对应的生成树的棵数为：
(n?1)nn?2?2nn?3，所以，K n - e 对应的生成树的棵数为：
1n(n?1)2?(Kn?e)?nn?2?2nn?3?(n?2)nn?3
16、Kruskal算法能否用来求：
（1）赋权连通图中的最大权值的树？
（2）赋权图中的最小权的最大森林？如果可以，怎样实现？
解：（1）不能，Kruskal算法得到的任何生成树一定是最小生成树。 （2）可以，步骤如下：
步骤一：选择边e1，是的?(e1)尽可能小；
步骤二：若已选定边e1,e2,...,ei，则从E\\{e1,e2,...ei}选取ei?1，使 a、G[{e1,e2,...ei?1}]为无圈图 b、?(ei?1)是满足a的尽可能小的权； 步骤三：当步骤二不能继续执行时停止；
习题三
3.设G是阶大于2的连通图，证明下列命题等价：
（1）G是块
（2）G无环且任意一个点和任意一条边都位于同一个圈上； （3）G无环且任意三个不同点都位于同一条路上。 证明：（1）→（2）：
错误!未找到引用源。是块，任取错误!未找到引用源。的一点错误!未找到引用源。，一边错误!未找到引用源。，在错误!未找到引用源。边插入一点错误!未找到引用源。，
使得错误!未找到引用源。成为两条边，由此得到新图G1，显然错误!未找到引用源。的是阶数大于3的块，由定理，错误!未找到引用源。中的u,v位于同一个圈上，于是错误!未找到引用源。中u与边错误!未找到引用源。都位于同一个圈上。 (2)→(3):
无环，且任意一点和任意一条边都位于同一个圈上，任取错误!未找到引用源。的点u，边e，若错误!未找到引用源。在错误!未找到引用源。上，则三个不同点位于同一个闭路，即位于同一条路，如错误!未找到引用源。不在错误!未找到引用源。上，由定理，错误!未找到引用源。的两点在同一个闭路上，在错误!未找到引用源。边插入一个点v，由此得到新图错误!未找到引用源。，显然错误!未找到引用源。的是阶数大于3的块，则两条边的三个不同点在同一条路上。 (3)→(1):
错误!未找到引用源。连通，若错误!未找到引用源。不是块，则错误!未找到引用源。中存在着割点错误!未找到引用源。，划分为不同的子集块错误!未找到引用源。,错误!
未找到引用源。,错误!未找到引用源。,错误!未找到引用源。无环，x?v1,y?v2，点错误!未找到引用源。在每一条错误!未找到引用源。的路上，则与已知矛盾，错误!未找到引用源。是块。
13、设H是连通图G的子图，举例说明：有可能k(H)> k(G). 解：通常错误!未找到引用源。.
(完整版)图论及其应用1-3章习题答案(电子科大)
