函授专升本-课程复习资料-计算机科学与技术离散数学-试题3套含答案.pdfVIP

P279（1）证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之

和。

P279（2）写出下图相对于完全图的补图。

P287（5）a-c1．分析图1，求：ABC

（1）从A到F的所有通路。

（2）从A到F的所有迹。

（3）A和F之间的距离。DEF

图1

P300(3)在下图中给出了一个有向图，试求该图的邻接

矩阵，并求出可达性矩阵和距离矩阵。

vv

21

v

s

v

3v

4

nK

P311(3)确定取怎样的值，完全图有一条欧拉回路。

n

P311(7)判断下图所示的图中是否有汉密尔顿回路。

P317(2)证明：小于30条边的平面简单图有一个结点度数小于等于４。

P327(3)(3)一棵树有n2个结点度数为2，n3个结点度数为3，…，nk个结点度数为k,问

它有几个度数为1的结点?

P327(6a)对于下图，利用Kruskal算法求一棵最小生成树。

12

9

87

56

43

10

P337(3)证明在完全二叉树中，边的总数等于2(n-1)，式中n是树叶数。

P337（5a）给定权1，4，9，16，25，36，49，64，81，100，构造一棵最优二叉树。

P279（1）证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之

和。

证明：设有向完全图具有n个结点，对任一结点v均有

i





degvdegvn1

ii

1nn







又因边数nn1degvdegv，故而

2ii

i1i1

nn

22

