文档视界 最新最全的文档下载
当前位置:文档视界 > 电子科技大学-图论第一次作业

电子科技大学-图论第一次作业

课本习题一:

电子科技大学-图论第一次作业

电子科技大学-图论第一次作业

。 证明:作映射f : v i ? u i (i=1,2….10)

容易证明,对"v i v j ? E ((a)),有f (v i v j,),=,u i,u j,?,E,((b))

(1£ i £

10, 1£j £ 10 ) 由图的同构定义知,图(a)与(b)是同构的。

● 5.证明:四个顶点的非同构简单图有11个。

证明:设四个顶点中边的个数为m ,则有:

m=0:

电子科技大学-图论第一次作业

m=1 :

m=2:

电子科技大学-图论第一次作业

m=3:

电子科技大学-图论第一次作业

m=4:

(a) v 23 4

(b)

电子科技大学-图论第一次作业

m=5:

m=6:

电子科技大学-图论第一次作业

因为四个顶点的简单图最多就是具有6条边,上面所列出的情形是在不同边的条件下的不同构的情形,则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。

● 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)是图序列

非负整数组12121(,,,),,2n n n i i d d d d d d d m π==≥≥≥=∑L L 是图序列的充要条件是:

?

11

12312(1,1,,1,,,)d d n d d d d d π++=---L L 是图序列 (5,4,3,2,2,0)是图序列,然而(5,4,3,2,2,0)不是图序列,所以(6,6,5,4,3,3,1)不是图序列。

● 12.证明:若δ≥2,则G 包含圈。

证明:下面仅对连通图的下的条件下进行证明,不连通的情形可以通过分成若干个连通的情形来证明。设V (G )={V 1,V 2,V 3,?V n },对于G 中的路V 1,V 2,V 3,?V n 若V k 与V 1邻接,则构成一个圈。若V i1,V i2,V i3,?V in 是一条路,由于δ≥2,因此,对于V in ,存在V ik 与之邻接,则V ik ,,?V in V ik 构成一个圈。

● 17.证明:若G 不连通,则G ?连通。 证明:对于任意的u,v ∈(G

?),若u 与v 属于G 的不同连通分支,显然u 与v 在G ?中连通;若u 与v 属于g 的同一连通分支,设w 为G 的另一个连通分支中的一个顶点,

则u 与w ,v 与w 分别在G

?中连通,因此,u 与v 在G ?中连通。 ● 18.证明:若e ∈E(G),则w (G )≤w (G ?e )≤w (G )+1.

证明:若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.

习题二:

1.证明:非平凡树的最长路的起点和终点均是1度的。

证明设P =v 1v 2…v k 是非平凡树T 中一条最长路,若d(v 1)≥2则v 1与v k 在T 中的邻接点只能有一个,否则,若v 1与除了P 中顶点之外的其他顶点相连,则P 可以继续延长,这与P 是最长路是相矛盾的。若v 1与P 上的某顶点相连,则就构成了圈,这与数相矛盾,推出P 不是最长路。即说明v 1与v k 是树叶,则v 1与v k 均是一度的。所以非平凡树的最长路的起点和终点均是1度的。

9.证明:顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。

证明:证明:由于G 是连通非平凡的且每个顶点度数为偶数,所以G 中至少存在圈C 1,从G 中去掉C 1中的边,得到G 的生成子图G 1,若G 1没有边,则G 的边集合能划分为圈。否则,G 1的每个非平凡分支是度数为偶数的连通图,于是又可以抽取一个圈。反复这样抽取,E(G)最终划分为若干圈。

设C 1是G 的边划分中的一个圈。若G 仅由此圈组成,则G 显然是闭迹。否则,由于G 连通,所以,必然存在圈C 2,它和C 1有公共顶点。于是,C 1∪C 2是一条含有C 1与C 2的边的欧拉闭迹,如此拼接下去,得到包含G 的所有边的一条闭迹.

16.Kruskal 算法能否用来求:

(1)赋权连通图中的最大权的树?

(2)赋权图中的最小权的最大森林?如果可以,怎样实现?

答:1、不能,由Kruskal 算法得到的任何生成树一定是最小生成树。

2、能

a.选择边e1使其权值最小

b.若已经选定边e1 e2 e3 ……ek,则从E-{e1,e2,e3……ek},选择边ek+1

c .G[e1,e2,e3……ek]为无圈图,且可以不连通

d .ek+1的权值w (eK+1)尽可能小

e .当a 、b 、c 不能进行时,停止。

习题三:

1.证明:e 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2,使对任意u ∈V 1及v ∈V 2, G 中的路(u ,v )必含e .

证明:必要性: e 是G 的割边,故G ?e 至少含有两个连通分支,设V 1是其中一个连通分支的顶点集,V 2是其余分支的顶点集,对12,u V v V ?∈?∈,因为G ?e

中的u,v 不连通,而在G 中u 与v 连通,所以e 在每一条(u,v)路上,G 中的(u,v)必含e 。

充分性:取12,u V v V ∈∈,由假设G 中所有(u,v)路均含有边e ,从而在G ?e 中

不存在从u 与到v 的路,这表明G ?e 不连通,所以e 是割边。

3.设G 是阶大于2的连通图,证明下列命题等价:

(1) G 是块

(2) G 无环且任意一个点和任意一条边都位于同一个圈上;

(3) G 无环且任意三个不同点都位于同一条路上。

(1)→(2):

G 是块,任取G 的一点u ,一边e ,在e 边插入一点v ,使得e 成为两条边,由此得到新图G 1,显然G 1的是阶数大于2的块,由定理4,G 1中的u,v 位于同一个圈上,于是G 中u 与边e 都位于同一个圈上。

(2)→(3):

G 无环,且任意一点和任意一条边都位于同一个圈上,任取G 的点u ,边e ,若u 不在e 上,则三个不同点位于同一个圈,即位于同一条路,如u 在e 上,由定理e 的两点在同一个圈上,在e 边插入一个点v ,使得e 成为2条边,由此得到新图G 1,显然G 1的是阶数大于2的块,则两条边的三个不同点在同一条路上。

(3)→(1):

G 连通,若G 不是块,则G 中存在着割点u ,划分为不同的子集块V 1, V 2, V 1, V 2无环,12,x v y v ∈∈,点u 在每一条(x,y)的路上,由于x,y 的任意性,则三个不同点不能位于同一条路上,则与已知矛盾,G 是块。

7.证明:若v 是简单图G 的一个割点,则v 不是补图G

?的割点。 证明: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 不是其补图的割点。

12.对图3——20给出的图G1和G2,求其连通度和边连通度,给出相应的最小点割和最小边割。

解:()12G κ= 最小点割 {6,8}

1()2G λ= 最小边割{(6,5),(8,5)} {(6,7),(8,7)}{(6,9),(8,9)}

()25G κ= 最小点割{6,7,8,9,10}

2()5G λ= 最小边割{(2,7),(1,6),(5,10),(4,9),(3,8)}

13.设H 是连通图G 的子图,举例说明:有可能k(H)> k(G).

解:

通常k(H)

e

H

整个图为G,割点e左边的图H为G的的子图,k(H)=3k(G)=1,则k(H)>k(G).

相关文档
  • 图论第一次作业

  • 电子科大图论答案

  • 图论作业

  • 电子科技大学专业

  • 图论作业1

  • 图论大作业

相关推荐: