一二章习题

11、证明：在n阶连通图中(1)至少有n-1条边；(2)如果边数大于n-1，则至少有一条闭迹；(3)如果恰有n-1条边，则至少有一个奇度点。证明:(1)若G中没有1度顶点，由握手定理：()2()21vVGmdvnmnmn若G中有1度顶点u，对G的顶点数作数学归纳。当n=2时，结论显然；设结论对n=k时成立。当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G的边数≥k.另证：由于G连通，所以，存在如下形式的途径：121nnvvvv显然该途径至少含有n-1条边。(v1,v2,…,vn是G的n个不同顶点)2(2)考虑G中途径：121:nnWvvvv若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于是：1iijivvvv为G中一闭途径，于是也就存在闭迹。(3)若不然，G中顶点度数至少为2，于是由握手定理：()2()21vVGmdvnmnmn这与G中恰有n-1条边矛盾！33.证明下面两图不同构。u1v1证明:u1的两个邻接点与v1的两个邻接点状况不同。所以，两图不同构。44.证明下面两图同构。证明:作映射f:vi↔ui(i=1,2….10)(a)v1v2v3v4v5v6v7v8v9v10u1u2u3u4u5u6u7u8u9u10(b)容易证明，对vivjE((a)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由图的同构定义知，图(a)与(b)是同构的。55.指出4个顶点的非同构的所有简单图。四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。68.设Δ和δ是简单图的最大度和最小度，则δ≦2m/n≦Δ证明：由握手定理可得1()2niindvmn所以δ≦2m/n≦Δ9.证明：若k正则偶图具有二分类V=V1∪V2,则|V1|=|V2|证明：根据定义可知，V1中所有结点关联的边就是偶图中所有的边，而且等于V2中所有结点关联的边。由该图的正则性可得k|V1|=k|V2|所以|V1|=|V2|712证明：若δ≥2，则G中必然含有圈。证明：只就连通图证明即可！设W=v1v2…..vk-1vk是G中的一条最长路。由于δ≥2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路，所以，这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为vm，则vmvm+1….vkvm为G中圈。11.解；（7,6,5,4,3,3,2）中对应了7个顶点，简单图中最大度应该为6，故不是图的度序列（6,6,5,4,3,3,1）中对应了7个顶点,有2个顶点度数为6，意味着这两个顶点和图中其余结点都是邻接的，所以其余顶点度数至少为2，故不是图的度序列813.证明若G是简单图，且δ≥2，则G含有长最小为δ+1的圈证明：设v1,v2,….,vk为G中最长路。则v1的邻点都在这条路上，否则与其为最长路矛盾。取v1的邻点下标最大者，记为l，显然l≥δ。于是v1,v2,….,vlv1为长最小为δ+1的圈.15.（1）仅对简单图做证明。若G中有1度点，则可以删除这些顶点及其相关联的边得到G1,而且m(G1)≥n(G1).若G1仍有1度点，重复上述过程。因为对于阶数为1或者2的简单图不可能满足m≥n，所以上述过程到某个Gk就停止了。此时Gk中结点度数至少为2，所以Gk中存在圈，G中也存在圈。17.证明因G是不连通,故G中至少两个分支.设u，v是G的任意两个顶点。若u和v在G中不邻接，则在中它们邻接。G若u和v在G中邻接，则它们属于G的同一分支。在另一个分支中取一点w，则在中u和v均与w邻接，从而uwv是一条通道,故在中它们邻接。GG9v1v2v3vn-2uv21.设G是具有m条边的n阶单图，证明：若G的直径为2且Δ=n-2,则m≥2n-4.证明：设d(v)=Δ=n-2,且设v的邻接点为v1,v2,…,vn-2.u是剩下的一个顶点。由于d(G)=2且u不能和v邻接，所以u必须和v1,v2…,vn-2中每个顶点邻接。否则有d(G)2.于是得：m≥2n-4.10习题21、证明：因为非平凡数无圈，且至少有两个1度点。由某个1度点出发，延长通路，直到无法继续延长，到另一个1度点结束。故非平凡树最长路的端点和终点度必为1.2、证明：设G为恰有两个1度点的树，则m=n-1，由握手定理221222,()()()()vVdvdvnn因为G连通，除两个1度点外，剩余n-2个顶点度数都大于2.根据上式可知，这该n-2个顶点度数只能为2，否则矛盾。于是G是路。3.证明：反证法，若G中度为1的顶点个数s小于k，则22121121()[()]vVmdvnsksnskn1mn与矛盾，假设不成立,命题得证114.设G是森林且恰有2k个奇数顶点，则在G中有k条边不重合的路P1,P2,…,Pk,使得：12()()()()kEGEPEPEP证明：对k作数学归纳。当k=1时，G只有两个奇数度顶点，此时，容易证明，G是一条路；设当k=t时，结论成立。令k=t+1在G中一个分支中取两个一度顶点u与v，令P是连接该两个顶点的唯一路，则G-P是有2t个奇数顶点的森林，由归纳假设，它可以分解为t条边不重合的路之并，所以G可以分解为t+1条边不重合的路之并。125.证明：必要性显然，下证充分性。1221()=(-),(,,,)nvVdvnddd因为所以可以根据构造一个图设G是满足该度序列连通分支最少的一个图，且m=n-1。假设G不连通，联通分支个数为w，则至少有一个连通分支有圈C；否则G是森林，且满足m=n-w,矛盾。从圈C中取一边e1=u1v1，并从另一连通分支中取一边e2=u2v2，构造图11221221‘-{,}{,}GGuvuvuvuv易知G‘的度序列仍为，且满足m=n-1对每个连通分支重复上述过程，直到其变为连通图为止。该图即为树。12(,,,)nddd136.设T是k阶树。若图G满足δ≧k-1,则T同构于G的某个子图。证明：对k作数学归纳。当k=1时，结论显然。假设对k-1(k≧3)的每颗树T1,以及最小度至少为k-2的每个图H，T1同构于H的某个子图F。现在设T是k阶树，且G是满足δ(G)≧k-1的图。我们证明T同构于G的某个子图。设u是T的树叶，v是u的邻接顶点。则T-u是k-1阶树。由于δ(G)≧k-1k-2，由归纳假设，T-u同构于G的某个子图F.设v1是在同构下与T中点v相对应的F中的点，由于dG(v1)≧k-1,所以v1在G中一定有相异于F中的邻点w,作F∪｛v1w｝,则该子图和T同构。v1wFG147.(1)证明：必要性：若e不是G的割边，则G-e连通，且在G-e中包含一颗生成树T。显然T也是G的生成树且不含e，和已知条件矛盾。故e是G的割边。充分性：若e是G的割边，且在G中存在一个不含e的生成树T。则T+e含一圈C，且e∈C，这与e是割边矛盾。从而e属于G的每个生成树。(2)证明：必要性：G具有生成树且e不属于任一个生成树，对于G的某个生成树T，T+e包含圈C。若C包含异于e的边e’,现构造T’=T+e-e’,显然T’连通，且边数为n-1，即T’是G的生成树且包含e，矛盾。所以C中不含异于e的边，即e是G中的环。充分性：若e是G中的环，根据树的定义，e一定不属于G的任意一个生成树。159.可以参照欧拉图的证明，这里给出一种构造性证明方法从任一结点开始构造包含所有边的回路：以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以回到原出发点而告终。如果图中所有的边已用这种方式经过了，显然这就是所求的包含所有边的回路。如果图中不是所有的边都经过了，去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。因为原来的图是连通的，因此，这个子图必与已经过的回路在一个或多个结点相接。从这些结点中的一个开始，再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的回路。1610.证明（1）反证法，若G中存在割边e，取G-e中含e的一个端点u的连通分支G1，则G1中除u的度数为奇数外，其余顶点度数均为偶数，这是不可能的，所以G中无割边。（2）设e是G的割边，对于G-e的一个连通分支G1，G1仍为偶图，且除一点的度数为k-1外，其余点都为k。假设G1的二分类所包含的顶点数分别为m和n，则有km=kn+1.但当k≥2时，上式不可能成立。矛盾，故G中无割边。11.（1）证明：设e=uv是G的割边，则按定义知1()()wGewG所以G-e包含两个连通分支G1和G2。由n≥3，不失一般性，可假设v∈G2，|V(G2)|≥2。所以1212(),()=GvGGvGGv且21(-)()wGvwG故（2）17131234123412341234123412341234123412341234123412341234123412341234