图论及应用第一章完整作业

习题11.证明在n阶连通图中（1）至少有n-1条边。（2）如果边数大于n-1，则至少有一条闭通道。（3）如恰有n-1条边，则至少有一个奇度点。证明(1)若对vV(G),有d(v)2,则：2m=d(v)2nmnn-1,矛盾！若G中有1度顶点，对顶点数n作数学归纳。当n=2时，G显然至少有一条边，结论成立。设当n=k时，结论成立，当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。(2)考虑v1v2vn的途径，若该途径是一条路，则长为n-1,但图G的边数大于n-1,因此存在vi,vj,使得viadgvj,这样，vivi+1vj并上vivj构成一条闭通道；若该途径是一条非路，易知，图G有闭通道。(3)若不然，对vV(G),有d(v)2,则：2m=d(v)2nmnn-1,与已知矛盾！2.设G是n阶完全图，试问（1）有多少条闭通道？（2）包含G中某边e的闭通道有多少？（3）任意两点间有多少条路？答(1)(n-2)!(2)(n-1)!/2(3)1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1.3.证明图1-27中的两图不同构：证明容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。4.证明图1-28中的两图是同构的证明将图1-28的两图顶点标号为如下的(a)与(b)图图1-27图1-28作映射f:f(vi)ui(1i10)容易证明，对vivjE((a)),有f(vivj)uiujE((b))(1i10,1j10)由图的同构定义知，图1-27的两个图是同构的。5.证明：四个顶点的非同构简单图有11个。证明m=0123456由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。6.设G是具有m条边的n阶简单图。证明：m=2n当且仅当G是完全图。证明必要性若G为非完全图，则vV(G),有d(v)n-1d(v)n(n-1)2mn(n-1)mn(n-1)/2=2n,与已知矛盾！充分性若G为完全图，则2m=d(v)=n(n-1)m=2n。7.证明：（1）m(Kl,n)=ln，（2）若G是具有m条边的n阶简单偶图，则m42n。(a)v1v2v3v4v5v6v7v8v9v10u1u2u3u4u5u6u7u8u9u10(b)证明(1)Kl,n的总度数为2ln,所以，m(Kl,n)=ln。(2)设G的两个顶点子集所含顶点数分别为n1与n2,G的边数为m,可建立如下的二次规划：m=n1n2s.tn1+n2=nn11,n21当n为偶数时，n1=n2=n/2时，m取最大值：m=n2/4当n为奇数时，取n1=(n+1)/2,n2=(n-1)/2时，m取最大值：m=(n2-1)/4所以，m42n。8.设△和δ是简单图G的最大度和最小度，则δ≤2m/n≤△。证明nmnmnvdmnmnvdmVvVv22)(22)(29.证明：若k正则偶图具有二分类V=V1∪V2，则|V1|=|V2|。证明由于G为k正则偶图，所以，kV1=m=kV2V1=V2。10.证明：由两人或更多个人组成的人群中，总有两人在该人群中恰好有相同的朋友数。证明将人用图的顶点表示，图的两顶点邻接当且仅当人群中的两人相认识，于是，问题转化为：证明在任意一个简单图中必有一对度数相等的顶点。若图G为连通单图，则对vV(G),有1d(v)n-1,因此，n个顶点中必存在两个顶点，其度数相同；若G为非连通图，设G1为阶数n1的连通分支，则vV(G1),有1d(v)n1-1，于是在G1中必存在两个顶点，其度数相同。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包含圈。证明只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，则构成一个圈。若vi1vi2…vin是一条路，由于2，因此，对vin，存在点vik与之邻接，则vikvinvik构成一个圈。13.证明：若G是简单图且δ≥2，则G包含长至少是δ+1的圈。证明设v0v1…vk为G中一条最长路，则v0的邻接顶点一定在该路上，否则，与假设矛盾。现取与v0相邻的脚标最大者，记为l，则l,于是得圈v0v1v2vlv0,该圈长为l+1，显然不小于δ+1。`14.G的围长是指G中最短圈的长；若G没有圈，则定义G的围长为无穷大。证明：（1）围长为4的k的正则图至少有2k个顶点，且恰有2k个顶点的这样的图（在同构意义下）只有一个。（2）围长为5的k正则图至少有k2+1个顶点。证明(1)设u,v是G中两相邻顶点，则S(u)S(v)=,否则，可推出G中的围长为3，与已知矛盾。因此，G中至少有2（k-1）+2个顶点，即有2k个顶点。把S(u)v，S(v)u连为完全偶图，则得到2k个顶点的围长为4的图，由作法知，这样的图是唯一的。(2)对uV(G),设u的邻接顶点为u1,u2,uk,由于G的围长为5，所以，u1,u2,uk互不邻接。又设ui的邻接顶点为ui1,ui2,uik-1,(i=1,2,…,k),显然，S(ui)S(uj)=u(ij),否则，G中有长为4的圈，所以，G的顶点数至少有k2+1个。15.对具有m条边的阶n图G，证明：（1）若m≥n，则G包含圈；（2）若m≥n+4，则G包含两个边不重的圈。证明（1）若G含有环或平行边，则G有圈。假定G为n阶简单图。若G中顶点度大于等于2，则G中有圈。设G中有一度顶点，去掉该顶点和其关联的边得图G1,由条件，显然有m(G1)V(G1),若G1中有一度顶点，去掉该顶点和其关联的边得图G2,有m(G2)V(G2),，如此进行下去，该过程不可能进行到n=1或n=2的情形，否则，不满足m≥n所以，过程进行到Gm,Gm是度数2的图，它含有圈。(2)只就m=n+4证明就行了。设G是满足m=n+4，但不包含两个边不相交的圈的图族中顶点数最少的一个图。可以证明G具有如下两个性质：1)G的围长g5。事实上，若G的围长4，则在G中除去一个长度4的圈C1的一条边，所得之图记为G,显然，m(G)V(G)=V(G),由(1),G中存在圈C2,使C1,C2的边不相交这与假定矛盾；2）(G)3。事实上，若d(v0)=2,设v0v1,v0v2E(G),作G1=G-v0+v1v2;若d(v0)1,则G1为在G中除去v0及其关联的边(d(v0)=0,任去G中一条边)所得之图。显然，m(G1)=V(G1)+4,G1仍然不含两个边不重的圈之图。但V(G1)V(G)，与假定矛盾。由2),n+4=m3n/2n8.但另一方面，由1),在G中存在一个圈Cg，其上的顶点之间的边，除Cg之外，再无其它边，以S0表示Cg上的顶点集，故由2),S0上每个顶点均有伸向Cg外的的边。记与S0距离为1的顶点集为S1，则S0的每一个顶点有伸向S1的边，反过来，S1中的每个顶点仅有唯一的一边与S0相连，不然在G中则含有长不大于g/2+2的圈，这与G的围长为g相矛盾，故S0S1,于是有：nS0+S1g+g10,但这与n8矛盾。所以，假定条件下的G不存在。16.在图1-13的赋权图中，找出a到所有其它顶点的距离。解1.A1={a}，t(a)=0，T1=Φ2.113bv3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(最小)，T2={av3}2.A2={a,v3},2)2(21)2(1,vbvb3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}2.A3={a,v3,v1},3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}2.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v53.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,v1v4,v4v5}2.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v23.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2}2.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，b5(6)=v6，b6(6)=v63.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，T7={av3,av1,v1v4,v4v5,v4v2,v2v6}2.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，b7(7)=b3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b}于是知a与b的距离d(a,b)=t(b)=11由T8导出的树中a到b路1426avvvvb就是最短路。17.证明：若G不连通，则G连通。4)3(32)3(22)3(1,,vbvbvbv11v463429a8v22v56b72412v3v6图1-139证明对)(,_GVvu,若u与v属于G的不同连通分支，显然u与v在_G中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在_G中连通，因此，u与v在_G中连通。18.证明：若e∈E(G)，则ω(G)≤ω(G-e)≤ω(G)+1。证明若e为G之割边，则ω(G-e)=ω(G)+1，若e为G之非割边，则ω(G-e)=ω(G)，所以，若e∈E(G)，则ω(G)≤ω(G-e)≤ω(G)+1。19.证明：若G连通且G的每个顶点的度均为偶数，则对于任意的v∈V(G)，ω(G-v)≤d(v)/2成立。证明设C为ω(G-v)的一连通分支，则在G中，v有偶数条边伸向C，若不然，C中奇度点个数为奇数。因此，v至少有两条边伸向C，有ω(G-v)≤d(v)/2成立。20.证明：若G的直径大于3，则G的直径小于3。证明)(,GVvu，若uvE(G)uvE(G)1),(vudG。若uvE(G)，则uvE(G)。分两种情况：(1)若在V(G)中任意顶点至少和u,v之一相连，在这种情况下，对G中任意两个顶点x,y，有，矛盾。(2)V(G)中存在一点w,使得uw,wvE(G),则uw,wvE(G)，此时，2),(vudG。所以，G的直径小于3。21．设G是具有m条边的n阶简单图，证明：若G的直径为2且△=n-2，则m≥2n-4。证明在G中，设d(v)=△=n-2,与v邻接的顶点设为：v1,v2,…,vn-2,剩下的一个顶点为u,u与v不能邻接。如下图所示。由于d(G)=2，因此u与v1,v2,…,vn-2必邻接，否则，G的直径大于2。因此，该图中至少应该有的边数为n-2+n-2=2n-4,即：m≥2n-4。22．证明：若G是至少有三个点的简单连通图但不是完全图，则G有三个顶点u,v和3),(yxdGv1v2v3vn-2uvw，使得uv,vw∈E，而uwE。证明G是非完全图u,w1V,uw1