（书后作业）集合论与图论

P307习题

1.设D是一个有p个顶点q条弧的有向图。若D是连通的，证明：p-1≤q≤p(p-1)。

2.设D是一个有p个顶点q条弧的强连通的有向图，则q至少是多大？

4.证明：有向图D是单向连通的当且仅当D有一条生成通道。

P307习题

2.有向图D的图解如图10.4.3所示 (1)写出D的邻接矩阵及可达矩阵； (2)写出D关联矩阵。

33

3.设D为图10.4.4中的有向图，试求v2到其余每个顶点的长≤4的所有通道的条数。

4.已知有向图D的邻接矩阵B，如何从B求D的可达矩阵R？

P321习题

1.设T是一个正则m元有序树，它有n0个叶子，T有多有多少条弧？

3.设T是一个有n0个叶子的二元树，出度为2的顶点为n2，试证：n0=n2+1。

4.具有三个顶点的有序树共有多少个？具有三个顶点的有根树有多个？注意，同构的只算一个。

8. 用数学归纳法证明每个比赛图中必有有向哈密顿路。

34