离散数学习题解答第6部分(图论)(2)

v3)，(v3，v9)，(v3，v4)})，

G2=({v4，v7，v8}，{(v7，v8)，(v8，v4)})， G3=({v5}，{v5，v5})，G4=({v6}，φ) 3）有三个弱连通支，它们是

G1=({v1，v2，v3，v4，v7，v8，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，

v1)，(v2，v3)，(v3，v9)，(v3，v4)，(v7，v8)，(v8，v4)}) G2=({v5}，{(v5，v5)})，G3=({v6，φ})

15．给出有向图如下所示： 1) 求它的邻接矩阵A；

2) 求A2，A3，A4，指出从v1到v4长度为

1，2，3，4的路径各有几条？

3) 求AT，ATA，AAT，说明ATA和AAT

中元素（2，3）和（2，2）的意义；

4) 求A(2)，A

（3）

v9 v8 v7

v

1

v2 ，A

（4）

及可过矩陈R；

v3

5) 求出强度通支。 [解] 1）它的邻接矩阵

0 0A

0 0 2) 0 0A2

0 0 0 03

A

0 0 0 0A4

0 0

101

011 101

100 101 0

011 0101 0

100 0

111 0

201 0111 0

011 0212 0

122 0212 0

201 0

101 0

011 0

101 0

100 0

101 0

011 0

101 0

100 0101 0

011 0

1010 100 0

111

201 111

011 212

122 212

201 323

413 323

122

从v1到v4长度为1的路有1条，是（v1，v4）；

从v1到v4长度为2的路有1条，是（v1，v2），（v2，v4）； 从v1到v4长度为3的路有2条，是： (v1，v2)，(v2，v8)，(v3，v4)； (v1，v4)，(v4，v2)，(v2，v4)。 从v1到v4长度为4的路有3条，是： (v1，v2)，(v2，v3)，(v3，v2)，(v2，v4)； (v1，v2)，(v2，v4)，(v4，v2)，(v2，v4)； (v1，v4)，(v4，v2)，(v2，v3)，(v3，v4)； 3）

0

T

A= 1

0 1

0011

0101

0 1 0 0

0000 0 1011 0

ATA

0100 0 1110 0 0101 00

0011 10

AAT

0101 01

0100 11

10110101

1 0

11 0

01 0

00 0

0 21

1 12

0 21

0 10

003022111

0011

0

2 1 3 1 0 0 1

在ATA中，元素（2，3）=0的意义是：

不存在着这样的结点，从它发出的边同时终止于结点v2及v3；

在ATA中，元素（2，3）=3的意义是：deg（v2）=3，即结点v2的入度为3。

在AAT中，元素（2，3）=1的意义是：存在着一个结点，v4从v2及v3发出的边同时终之于它；

在AAT中，元素（2，2）=2的意义是：deg（v2）=2，即结点v2的出度为2。 4）

A(2)

0

0 0 0 0 0 0 0 0 0 0 0

10111110

01001111

1 0 01 1 0 0 01 0 01 1 0 1 0

101110111011

0100010101011111

A(3)

1 0

01 1 0 0 01 0

01 1 0 0 0

0 0 0 0

11101111

1110

1011

1 1 1 1 1 1 1 1

A(4)

111 0

0111

111 0

111 0

R A A(2) A(4)

0 0 0 0

1 1 1 0 11 11 11

11

111 111 111

111

5）·强连通支为 G1=（{v1}，φ）

G2=（{v2，v3，v4}，{(v2，v3)，(v2，v4)，(v3，v2)，(v3，v4)，(v4，v2)}） 16．利用Dijkstra算法，求出下面图中从u到v的所有最短路径及路径长度。

10

u

v

（1）

(a)

∞ v

(b)

(c)

(d)

(e)

(f)

(g)

(h)

u4

从u到v的最短路径共有三条： P1=(u,u1,u3,u4,v)

P2=(u,u1,u2,u3,u5,u6,v) P3=(u,u12,u2,u3,u6,v) P4=(u,u1,u2,u3,u5,u8,u6,v) P5=(u,u7,u8,u6,v)

从u

到v的最短路长为： W(P1)=W(P2)=W(P3)=15。

u1

(j)

（2）

(a)

(b)

(c)

(d)

(e)

(f)

(g)

17．在Dijjkstra算法中，增加一个记忆系统，使得此算法不仅能给出从u到v的最

短路的路长，而且可以给出一条最短路径。

[解] 观察Dijkstra算法的，容易看出每当确定出一个新的标记点t0 时，由初始

结点u到结点t0的最短路就可以确定下来了（但可能不唯一）。因而，该路中心至少有一点P。直接与结点t0相邻。故此，修正的算法如下： 算法一：在确定从结点u到结点v的最短路的路长的同时， ：={u}；T：=V\P；S(u)：=[u]；d(u)：=0；

( t∈T)(d(t)：=∞)

t∈T)(d(t)：=min{d(t)，d(P)+W(P，t)}；

p P

( t0∈T)( t∈T)(d (t0)≤d(t))； ( P0∈P)(d(t0)=d(p0)+W(p0，t0))；

S(t0)：=[S(p0) | t0]； （表结构）

：=PU{t0}；T：=T\{t0}；mark(t0)：=d(t0) t0=v then exit else goto ； 我们也可以采用回溯方法。

算法二：在Dijkstra算法之后增加一个回溯系统，求出一条从u到v的最短路径。

：={u}；T：=V\P；d(u)：=0；( t∈T)(d(t)：=∞)； t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；

p P

( t0∈T)( t∈T)(d(t0)≤d(t))；

：=PU{t0}；T：=T\{t0}；mar(t0)：=d(t0) ：=[v]；g：=v

p∈P)(d(p)=d(g)=W(p，q))； s：=[p | s]； q：=p；

以上两种算法都直接给出了从结点u到结点v的最短路径。但是，算法一的记忆比较庞大，而算法二又重复了Dijkstra算法中的一些判断过程。我们综合以上两种算法，又有如下

算法三：在求出从结点u到结点v的最短路径之间各结点的最短长度d值以及前驱结点（紧前结点）

：= {u}；T：=V\P；d(u)：=0；( t∈T)(d(t)：=∞)； t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；

p P

( t0∈T)( t∈T)(d(t0)≤d(t))； ( p∈P)(d(p)=d(p0)+w(p0，t0))；

：=PU{t0}；T：=T\{t0}；mark(t0)：=(p0，d(t0))； t0=v then exit else goto ；

算法三并未直接给出从结点u到结点v的最短路径，但它的记忆系统比较简单，计算方便。要给出从结点u到v的最短路经时，只要从终步v开始，根据标记的第一个分量，向前回溯即可得到。 18．判断下列图示能否一笔画。

b

c

[解] 根据本章§2定理2：图中奇结点的个数是偶数。所以奇结点的个数为2k，当

k=0，1时，此图是一笔画的，而当k＞1时，则此图是k笔画的。于是 图(a)，不是一笔画，因为它的奇结点为四个（用○·表示）； 图（b），（c）都是一笔画，因为它的奇结点是二个；

19．设G是有向图，证明G是Euler图的充要条件是：G是强连通的，且G中每一

结点的进度等于出度。 [证] 必要 …… 此处隐藏：2803字，全部文档内容请下载后查看。喜欢就下载吧 ……