图论第二次上交作业.docx

班级：1班 姓名：关科科 学号：201421260251 1.4 证： 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(vi)?ui (1? i ? 10)。可证明，对?vivj?E((a)),有f(vivj)?uiuj?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图中两个图是同构的。 1.5 证： 因为四个顶点的简单图最多有六条边，可以列举出所有的情况如下： 可以得到非同构图最多有11个。 1.11 证： 因为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）不是图序列。 1.12 证： δ≧2,在图G中任取一点u，则d(u)≧2.存在u1≠u与u相邻接。由于d(u) ≧2，则存在u2≠u与u1邻接，由于图是有限图，如此下去定会返回u，由圈的定义可知图G包含圈。 1.17 证： 设u、v是G的任意两个顶点。若u和v在G中不邻接，则在 中他们邻接。若u和v在G中邻接，他们属于G的同一分支。在另一个分支中有一点w，在 中u和v均与w邻接，即uwv是一条通路，故是连通图。 1.18 证： 若e为G的割边，则w(G-e)= w(G)+1,若e不为G的割边，则w(G-e)= w(G)，所以，若e∈E(G),则w(G)≤w(G-e)≤w(G)+1。 2.1 证： 设u, v分别为非平凡树的起点与终点，若（u, v）路的起点或终点的度大于1，因为树无圈，可知（u, v）路可以继续延长。所以非平凡树的最长路的起点与终点均是1度的。 2.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的所有边的一条回路。 2.16 证： 对于（1）和（2）都可以用Kruskal算法。具体用法是：对（1）有两种方法： 1把Kruskal算法中的“小”字换为“大”字。 2重新规定图的权为： W’(e)=1/w(e) 当w(e)≠0 M（充分大） 当w(e)＝0 这样就可直接用Kruskal算法。 对于（2），只需要对G的每一分支施行Kruskal算法。 3.1证： 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.3证： （1）→（2）G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G1，显然G1的是阶数大于3的块，由定理，G中的u ,v位于同一个圈上，于是G1中u与边e都位于同一个圈上。 （2）→（3）G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u，边e，若u在e上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v，由此得到新图G1，显然G1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V1，V2，V1，V2无环，x∈v1，y∈v2，点u在每一条（x，y）的路上，则与已知矛盾，G是块。 3.7证：v是单图G的割点，则G-v至少两个连通分支。现任取x,y∈V(G-v), 如果x,y在G-v的同一分支中，令u是与x,y处于不同分支的点，那么，通过u，可说明，x,与y在G-v的补图中连通。若x,y在G-v的不同分支中，则它们在G-v的补图中邻接。所以，若v是G的割点，则v不是其补图的割点。 3.12解： 最小点割 {6,8} 最小边割{（6,5），（8,5）} {（6,7），（8,7）}{（6,9），（8,9）}