（1)写出可行区域D中的所有顶点;（2)证明若一个线性规划问题在两个顶点上达到最优值，则此线性规

证明线性规划在可行区域不空的条件下只有两种可能结果：（1）目标函数值无下界；（2）所有可行解对应的目标函数值都相等，从而都是最优解。

程分为若于阶段，每一阶段选取若干条边.算法思路如下：

(1)将每个顶点视为一棵树，图中所有顶点形成一个森林;

(2)为每棵树选取一条边，它是该树与其他树相连的所有边中权值最小的一条边，把该边加入生成树中。如果某棵树选取的边已经被其他树选过，则该边不再选取。

重复以上操作，直到整个森林变成一棵树。

以图8-44所示的图为例，写出执行以上算法的过程。

对于如图8-5所示的有向图，试写出：

(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;

(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树。

间的一条最短路径，假设从初始顶点到目标顶点之间存在路径。现有一种解决该问题的方法：

(1)设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;

(2)选择离u最近且尚未在最短路径中的一个顶点v，加人到最短路径中，并修改当前结点u=v;

(3)重复步骤(2)，直到u是目标顶点时为止。

请问上述方法能否求解最短路径？若该方法可行，请证明之;否则请举例说明。

A.线性规划问题可能没有可行解

B.在图解法上，线性规划问题的可行解区域都是“凸”区域

C.线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达

A.2，1

B.1，2

C.1/2，1

D.1，1/2

作适当的变换,计算下列二重积分:

(1),其中D是平行四边形闭区域,它的四个顶点是(π,0),(2π,π),(π,2π)和(0,π);

(2),其中D是由两条双曲线xy=1和xy=2,直线y=x和y=4x所围成的在第I象限内的闭区域;

(3),其中D是由x轴、y轴和直线x+y=1所围成的闭区域;

(4),其中

设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).

(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:

式中,a(u,v)是边(u,v)的费用.

(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.