图论作业1.docxVIP

习题一： 4. 证明下面两图同构。 证明:作映射f : vi ? ui (i=1,2….10) 容易证明，对vi v j ?E ((a)),有f (v i vj,),=,ui,uj,?,E,((b)) (1￡ i ￡ 10, 1￡j￡ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m，则有： m=0: m=1 ： m=2： m=3： m=4： m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 非负整数组是图序列的充要条件是： 是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设VG={V1，V2,V3,?Vn},对于G中的路V1，V2,V3,?Vn若Vk与V1邻接，则构成一个圈。若Vi1，Vi2,Vi3,?Vin是一条路，由于δ≥2，因此，对于Vin，存在Vik与之邻接，则Vik，,?VinVik构成一个圈。 17.证明：若G不连通，则G连通。 证明：对于任意的u,v∈(G),若u与v属于G的不同连通分支，显然u与v在G中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在G中连通，因此，u与v在G中连通。 18.证明：若e∈E(G),则wG≤wG-e≤wG+1. 证明：若e为G的割边，则wG-e= wG+1，若e为G的非割边，则wG-e=wG，所以，若e∈E(G)，则有wG≤wG-e≤wG+1. 习题二： 证明：非平凡树的最长路的起点和终点均是1度的。 证明设P=v1v2…vk是非平凡树T中一条最长路，若d(v1)≥2则v1与vk在T中的邻接点只能有一个，否则，若v1与除了P中顶点之外的其他顶点相连，则P可以继续延长，这与P是最长路是相矛盾的。若v1与P上的某顶点相连，则就构成了圈，这与数相矛盾，推出P不是最长路。即说明v1与vk是树叶，则v1与vk均是一度的。所以非平凡树的最长路的起点和终点均是1度的。 9.证明：顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。 证明：证明：由于G是连通非平凡的且每个顶点度数为偶数，所以G中至少存在圈C1,从G中去掉C1中的边，得到G的生成子图G1,若G1没有边，则G的边集合能划分为圈。否则，G1的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。反复这样抽取，E(G)最终划分为若干圈。 设C1是G的边划分中的一个圈。若G仅由此圈组成，则G显然是闭迹。否则，由于G连通，所以，必然存在圈C2,它和C1有公共顶点。于是，C1∪C2是一条含有C1与C2的边的欧拉闭迹，如此拼接下去，得到包含G的所有边的一条闭迹. 16.Kruskal算法能否用来求： （1）赋权连通图中的最大权的树？ （2）赋权图中的最小权的最大森林？如果可以，怎样实现？ 答：1、不能，由Kruskal算法得到的任何生成树一定是最小生成树。 2、能 a.选择边e1使其权值最小 b.若已经选定边e1 e2 e3 ……ek，则从E-{e1，e2，e3……ek}，选择边ek+1 c．G[e1,e2,e3……ek]为无圈图，且可以不连通 d．ek+1的权值w（eK+1）尽可能小 e．当a、b、c不能进行时，停止。 习题三： 证明：e是连通图G的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u∈V1及v∈V2, G中的路（u，v）必含e. 证明：必要性: e是G的割边，故G-e至少含有两个连通分支，设V1是其中一个连通分支的顶点集，V2是其余分支的顶点集，对 QUOTE ，因为G-e中的u,v不连通，而在G中u与v连通，所以e在每一条(u,v)路上，G中的(u,v)必含e。 充分性：取 QUOTE ，由假设G中所有(u,v)路均含有边e，从而在G-e中不存在从u与到v的路，这表明G-e不连通，所以e是割边。 3.设G是阶大于2的连通图，证明下列命题等价： G是块 G无环且任意一个点和任意一条边都位于同一个圈上； G无环且任意三个不同点都位于同一条路