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

二（8分）

证明：对于 ν≥2\nu \geq 2 的图 GG ，若 ε≤ν−2\varepsilon \leq \nu - 2 ，则 GG 不连通。

三（10分）

用所附算法求下图中最优生成树（边旁的数字表示权重）。

第三题图

第三题图

附：Prim算法（令 SS 为当前子树的顶点集合，EE 为当前子树的边的集合，w(uv)w(uv) 为边 uvuv 的权重，d(v)d(v) 为点 vv 到 SS 的最小距离。）

  1. k=0k = 0 ，任取 ν∈V(G)\nu \in V(G) ，令 ν0=ν\nu_{0} = \nu ， S={ν0},E=∅S = \{\nu_0\}, E = \emptyset ， d(ν0)=0d(\nu_0) = 0 ， d(ν)=∞(ν≠ν0)d(\nu) = \infty (\nu \neq \nu_0)
  2. 若 S=V(G)S = V(G) ，结束（SS 与 EE 分别为最优树的顶点集与边集）；否则，转 2。
  3. 对任意的 ν∈V(G)∖S\nu \in V(G) \setminus S ，计算 d(ν)=min⁡{w(vkν),d(ν)}d(\nu) = \min \{w(v_k\nu), d(\nu)\}；对所有的 ν∈V(G)∖S\nu \in V(G) \setminus S ，计算 min⁡{d(ν)∣ν∈V(G)∖S}\min\{d(\nu) \mid \nu \in V(G) \setminus S\} ，令 νk+1\nu_{k+1} 为最小值点，若 d(νk+1)=∞d(\nu_{k+1}) = \infty ，则图 GG 不连通，结束（GG 没有生成树）；否则，选取边 νk+1\nu_{k+1} （其中 ν∈S\nu \in S ， w(νk+1)=d(νk+1)w(\nu_{k+1}) = d(\nu_{k+1})），令 S=S∪{νk+1}S = S \cup \{\nu_{k+1}\} ， E=E∪{νk+1}E = E \cup \{\nu_{k+1}\} ，令 k:=k+1k := k + 1 ，转 1。

四（12分）

用所附算法求下面赋权完全偶图 G=(X,Y;E)G = (X,Y;E) 中的最优匹配（权重最大的完美匹配）。 M=(mij)M = (m_{ij}) ，其中 mijm_{ij} 表示边 (xi,yj)(x_i, y_j) 的权重。

[458101176574851296661310745798]\left[ \begin{matrix} 4 & 5 & 8 & 10 & 11 \\ 7 & 6 & 5 & 7 & 4 \\ 8 & 5 & 12 & 9 & 6 \\ 6 & 6 & 13 & 10 & 7 \\ 4 & 5 & 7 & 9 & 8 \end{matrix} \right]

附：对赋权完全偶图 G=(X,Y;E)G = (X,Y;E) ，以 GG 的任意 f.v.l. ll 作为开始。 定 GlG_{l} ，并在 GlG_{l} 上任取一匹配 MM （可为 ∅\varnothing）作为开始的匹配。

（1）若 MM 饱和 XX 的每个顶点，则 MM 为最优匹配，停止；否则，任取一 MM-不饱和顶点 uu ，令 S={u}S = \{u\} ， T=∅T = \varnothing。

（2）若 NGl(S)⊃TN_{G_l}(S) \supset T ，转到（3）；否则， NGl(S)=TN_{G_l}(S) = T。计算 αl=min⁡x∈S,y∈T{l(x)+l(y)−w(xy)}\alpha_l = \min_{x \in S, y \in T} \{l(x) + l(y) - w(xy)\} 及 f.v.l. l~:l~(v)={l(v)−αl,v∈Sl(v)+αl,v∈Tl(v),其它\widetilde{l}: \widetilde{l}(v) = \begin{cases} l(v) - \alpha_l, & v \in S \\ l(v) + \alpha_l, & v \in T \\ l(v), & \text{其它} \end{cases}，令 l=l~l = \widetilde{l} ， Gl=Gl~G_l = G_{\widetilde{l}}。

（3）选取 y∈NGl(S)∖Ty \in N_{G_l}(S) \setminus T ，若 yy 为 MM-饱和的，设 yz∈Myz \in M ，则令： S=S∪{z}S = S \cup \{z\} ， T=T∪{y}T = T \cup \{y\} ，转（2）；否则， yy 为 MM-不饱和的，存在 MM-可扩路 PP ，令 M=MΔE(P)M = M \Delta E(P) ，转到（1）。

附：对赋权完全偶图 G=(X,Y;E)G = (X,Y;E) ，如果 GG 的顶点标号 l(v),v∈V(G)l(v), v \in V(G) 满足：对 ∀x∈X,y∈Y\forall x\in X, y\in Y 都有 l(x)+l(y)≥w(xy)l(x) + l(y)\geq w(xy) ，其中 w(xy)(≥0)w(xy) (\geq 0) 为边 xyxy 的权重，则称 ll 为 GG 的可行顶点标号，简记为 GG 的 f.v.l.。

对任意赋权完全偶图，可行顶点标号总是存在的，例如：

{l(x)=max⁡y∈Y{w(xy)}∀x∈Xl(y)=0\left\{ \begin{array}{l} l(x) = \max_{y \in Y} \{w(xy)\} \forall x \in X\\ l(y) = 0 \end{array} \right.

记： El={xy∈E∣l(x)+l(y)=w(xy)}E_{l} = \{xy \in E \mid l(x) + l(y) = w(xy)\} ，并称以 ElE_{l} 为边集的 GG 的生成子图为相等子图（equality subgraph），记为 GlG_{l}。