计算题

若自然数序列（d1，d2，…，dn）满足d1＞d2＞…＞dn，则当它为一简单无向图的度序列时有

问答题证明：序列（6，5，5，4，3，2，2），（7，6，5，4，3，3，2）以及（6，6，5，4，3，3，1）都不是简单无向图的度序列。

问答题（x）（P（x）→Q（y））

问答题Prim算法是另一个求最小生成树的算法，它的基本思想是：从任选一个结点v0（T0）开始，用最小代价连接v0与v0之外的某个结点，得子树T1，再用最小代价连接T1上某个结点与T1之外某个结点得到子树T2，如继续下去，直到所有的结点都被连接起来为止．用Prim算法求如图所示的最小生成树．

问答题n个结点的非连通简单无向图的边数最多可为多少？最少呢？

问答题当δ（G）≥1 2（n+k-1）时，证明G是k-连通图．