屈婉玲高教版离散数学部分答案2[1](1)(9)

31、设图 G 和它的部图 G 的边数分别为 m 和 m ，试确定 G 的阶数。

解： m

2 得 n

2 45、有向图 D 如图

(1)求 v2 到 v5 长度为 1，2，3，4 的通路数；

(2)求 v5 到 v5 长度为 1，2，3，4 的回路数；

(3)求 D 中长度为 4 的通路数； (4)求 D 中长度小于或等于 4 的回路数； (5)写出 D 的可达矩阵。

v4

v3

解：有向图 D 的邻接矩阵为：

0 0 0 0 1 0 1

0 1 0 2 0

1 0 1 0 0 0 0 0 0 2 0 2

A 0 0 0 0 1 ， A 2 0 1 0 1 0 A 3

2 0 1 0 1 0 0 0 0

0 0 2 0 2

0 1 0 1 0 2 0

2 0 0

0 0 0 0 0 0 4

4 0 4 0 0

0 1 2 1

5 2 5 2 A4 0 0 0 0 4 A A2 A 3 A 4

2 0 4 0

1 2 1

4 0 4 2 5 2

0 4 0 4 0

2 5 2 5 (1) v2 到 v5 长度为 1，2，3，4 的通路数为 0,2,0,0； (2) v5 到 v5 长度为 1，2，3，4 的回路数为 0,0,4,0；

(3)D 中长度为 4 的通路数为 32； (4)D 中长度小于或等于 4 的回路数 10；

2 0 0

0 2 0

2 0 0 0 2 0 0 0 4 5 2 5 2 4

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新IT计算机屈婉玲高教版离散数学部分答案2[1](1)(9)全文阅读和word下载服务。