24-25-1-图论及其应用-期末

二、（10分）

证明：图 GG 为 Hamilton 图，则：对任意非空的 S⊂VS\subset V，都有 ω(G−S)≤∣S∣\omega(G-S)\le\left|S\right|。

（其中 ω(G−S)\omega(G-S) 表示 G−SG-S 的连通分支数，∣S∣\left|S\right| 表示 SS 的顶点数。）

三、（10分）

第三题图

第三题图

用所附算法求下图中从 V0V_0 点到其他任意一点的最短路线及距离（弧旁的数字表示弧的距离）。

附 Bellman-Ford 算法：

{ui(1)=w0,i,  Pr⁡(i)=0i=0,1,⋯ ,v−1ui(k+1)=min⁡0≤j≤v−1{uj(k)+wj,i},  if ui(k+1)<ui(k),  Pr⁡(i)=li=0,1,⋯ ,v−1\begin{cases} u_i^{(1)}=w_{0,i},\;\operatorname{Pr}(i)=0&i=0,1,\cdots,v-1\\ u_i^{(k+1)}=\min_{0\le j\le v-1}\{u_j^{(k)}+w_{j,i}\},\;\text{if}\,u_i^{(k+1)}<u_i^{(k)},\;\operatorname{Pr}(i)=l&i=0,1,\cdots,v-1 \end{cases}

（其中 ll 为在 min⁡0≤j≤v−1{uj(k)+wj,i}\min_{0\le j\le v-1}\{u_j^{(k)}+w_{j,i}\} 中取到最小值的下标）

四、（10分）

设赋权完全图 GG 的邻接矩阵为

(0563525160560215778703521035686825735051615178685101360706861130)\left(\begin{matrix} 0&56&35&2&51&60\\ 56&0&21&57&78&70\\ 35&21&0&35&68&68\\ 2&57&35&0&51&61\\ 51&78&68&51&0&13\\ 60&70&68&61&13&0 \end{matrix}\right)

用如下近似算法求出图 GG 的一个 Hamilton 圈：

  1. 求 GG 中的一棵最小生成树 TT；
  2. 将 TT 中各边均加一条与原边权值相同的平行边，设所得图为 G′G'，显然 G′G' 是欧拉图。
  3. 求 G′G' 中的一条欧拉环游 EE；
  4. 在 EE 中按如下方法求从顶点 vv 出发的一个 Hamilton 圈 HH：从 vv 出发，沿 EE 访问 G′G' 中各个顶点，在没有访问完所有顶点之前，一旦出现重复出现的顶点，就跳过它走到下一个顶点。（称这种走法为抄近路走法。）