班级：1班姓名：关科科学号：201421260251
1.4 证：
将图1-28的两图顶点标号为如下的(a)与(b)图。
作映射f : f(vi)ui (1 i 10)。可证明，对vivje((a)),有f(vivj)uiuje((b)) 1 i 10, 1j 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 证：
由于是连通非平凡的且每个顶点度数为偶数，所以中至少存在圈，从中去掉中的边，得到的生成子图，若没有边，则的边集合能划分为圈。否则，的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。反复这样抽取，最终划分为若干圈。
设是的边划分中的一个圈。若仅由此圈组成，则显然是闭迹。否则，由于连通，所以，必然存在圈，它和有公共顶点。
于是，是一条含有与的边的欧拉闭迹，如此拼接下去，得到包含的所有边的一条回路。
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证：是连通图g的割边当且仅当v(g)可划分为两个子集v1和v2，使对任意及， g中的路必含。
证明：必要性： 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。
充分性：取，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以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证：是单图的割点，则至少两个连通分支。
现任取， 如果在的同一分支中，令是与处于不同分支的点，那么，通过，可说明，与在的补图中连通。若在的不同分支中，则它们在的补图中邻接。所以，若是的割点，则不是其补图的割点。
3.12解：
最小点割 最小边割
最小点割。最小边割。
3.13解：
通常。整个图为，割点左边的图为的的子图， ，则。
图论第二次作业
1 某乡 计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表所示。乡镇府如何选择修建公路的路线使总成本最低。2在下图中，求a到h i的最短路及最短路长，并对图 a 和 b 的结果进行比较。图。3已知某设备可继续使用5年，也可以在每年年末...
图论第二次作业
习题43 解 7.证明 将g中孤立点除去后的图记g1，则g1也无奇数度点，且 g1 2,从而可知g1有一个圈c1，在图g1 c1中去孤立点，得图g2 显然g2仍无奇数点，且 g2 2,所以g2中有一圈c2，如此下去，直至gm中有圈cm,且gm cm全为孤立点为止。于是e g e c1 e c2 e ...
图论第二次作业
第四章。3 1 有欧拉闭迹和h圈。2 有欧拉闭迹但没有h圈。3 有h圈无欧拉闭迹。4 无欧拉闭迹且没有h圈。4 证 若g不是h图，由chvatal定理知，g度弱于某个图，故 这与题目已知条件相矛盾，故g是h图。8 证 不失一般性，设g是连通图，是g的2k个奇点，连接，得到，则得到图，则是欧拉图，设c...