图论第二次上交作业

发布 2022-07-12 18:25:28 阅读 7332

班级: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...