2、有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。11.证明：序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是图序列。证明：由于7个顶点的简单图的最大度不会超过6,因此序列(7,6,543,3,2)不是图序列；(6,6,5,4,3,3,1)是图序歹ij坷二仏一1,〃37…4+i-14+2厂皿)是图序列(5,43,2,2,0)是图序列，然而(5,4,3,2,2,0)不是图序列，所以(6,6,5,4,3,3,1)不是图序列
3、。11.证明：若622,则G包含圈。证明只就连通图证明即可。设V(GHvl,v2,...,vn｝,对于G中的路vlv2...vk,若vk与vl邻接，则构成一个圈。若vilvi2...vin是一条路，由于2,因此，对vin,存在点vik与之邻接，贝!jvik…vinvik构成一个圈。17.证明：若G不连通，则乙连通。证明对也，圧WO,若u与v属于G的不同连通分支，显然u与v在。中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w,v与w分别在°中连通，因此，u与v在&中连通。1&
4、证明:若*E(G),则d5、成一个包含所有边的冋路。证明：证明：由于G是连通非平凡的且每个顶点度数为偶数，所以G中至少存在圈G,从G中去掉G中的边，得到G的生成子图G］,若G］没有边，则G的边集合能划分为圈。否则，Gi的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。E(G)反复这样抽取，最终划分为若干圈。设G是G的边划分中的一个圈。若G仅由此圈组成，则G显然是回路。否则，由于G连通，所以，必然存在圈C2,它和Ci有公共顶点。于是，CjUC2是一条含有G与C2的边的欧拉回路，如此拼接下去，得到包含G的所有边的一条回路.16.K
6、ruskal算法能否用来求：赋权连通图中的最大权值的树？赋权图屮的最小权的最大森林？如果可以，怎样实现？解：(1)不能，Kruskal算法得到的任何生成树一定是最小生成树。(2)可以，步骤如下：步骤一：选择边el,是的⑵(弓)尽可能小；步骤二若已选定边el9e29...9ei,则从E｛el9e29...ei｝选取弓+】,使G［｛®0,・・&+
7、｝］为无圈图e(X+i)是满足a的尽口」能小的权;步骤三：当步骤二不能继续执行时停止；习题31.证明：召是连通图G的割边当且仅当V(G)可划分为两个子集VI和V2,使
8、对任意u£加S中的路(u.丫)必含0.证明：充分性：召是G的割边，故G-e至少含有两个连通分支，设V】是其中一个连通分支的顶点集，匕是其余分支的顶点集，对Vf/eVpVveK，因为G中的un不连通，而在G中u与v连通，所以◎在每一条(口町路上，G中的(un)必含氐必要性：取wgV/,vgV2,由假设G中所有(q◎路均含有边已从而在G-e中不存在从u与到V的路，这表明G不连通，所以e是割边。3.设G是阶大于2的连通图，证明下列命题等价：(1)G是块(2)0无环且任意一个点和任意一条边都位于同一个圈上；(3)0无
9、环且任意三个不同点都位于同一条路上。(!)->⑵：G是块，任取G的一点u,—边在e边插入一点v,使得©成为两条边，由此得到新图S，显然％的是阶数大于3的块，由定理，G中的u,v位于同一个圈上，于是G]中u与边©都位于同一个圈上。⑵―(3)：G无环，.且任意一点和任意一条边都位于同一个圈上，任取G的点u,边e,若U在&上，则三个不同点位于同一个闭路，即位于同一条路，女HU不在0上，由定理，e的两点在同
