京都大学 情報学研究科 数理工学専攻 2014年8月実施 アルゴリズム基礎

标签：

• 京都大学
• 最短路径问题

Author

祭音Myyura

Description

$G = (V, E)$ を節点集合 $V$、枝集合 $E$ から成る連結な単純無向グラフとし、節点 $u$ の隣接の集合を $N(u)$ と書く。 $G$ の部分グラフ $H$ における節点 $u$ から節点 $v$ への最短路内の枝数を $\text{dist}_H(u,v)$ と書き、$H$ における節点 $u$ から節点 $v$ への最短路の総数を $\sigma_H (u,v)$ と書く。 始点 $s \in V$ を選び、$T$ を $s$ からの幅優先探索により得られた $G$ の全域木とする。 以下の問いに答えよ。

(i) $T$ を用いて、$d_{\max} = \max \{\text{dist}_G(s,u) \mid u \in V\}$ および $V_i = \{u \in V \mid \text{dist}_G(s, u)=i\}$, $i=0,1,\ldots, d_{\max}$ を $O(|V|)$ 時間で計算する方法を示せ。

(ii) $\{\sigma_G(s, u) \mid u \in V\}$ 内のすべての値を $O(|E|)$ 時間で計算する方法を示せ。

(iii) ある節点 $t \in V - \{s\}$ と節点の部分集合 $A \subseteq V - \{s,t\}$ に対して、$G$ における $s$ から $t$ への最短路のうち、$A$ の節点を１個は通過するものの個数を $O(|E|)$ 時間で計算する方法を示せ。

(iv) ある節点 $t \in V - \{s\}$ と節点の部分集合 $A \subseteq V - \{s,t\}$ に対して、$G$ における $s$ から $t$ への最短路のうち、$A$ の節点を少なくとも２個通過するものが存在するかどうかの判定を $O(|E|)$ 時間で計算する方法を示せ。

题目描述

设 $G=(V,E)$ 为由顶点集 $V$ 和边集 $E$ 构成的连通简单无向图，$N(u)$ 表示顶点 $u$ 的邻接点集合。对 $G$ 的子图 $H$，以 $\operatorname{dist}_H(u,v)$ 表示 $H$ 中从 $u$ 到 $v$ 的最短路边数，以 $\sigma_H(u,v)$ 表示这类最短路的总条数。选定起点 $s\in V$，令 $T$ 为从 $s$ 进行广度优先搜索得到的 $G$ 的生成树。回答：

1. 利用 $T$，在 $O(|V|)$ 时间内计算
   $$d_{\max}=\max\{\operatorname{dist}_G(s,u)\mid u\in V\}$$
   以及每一层
   $$V_i=\{u\in V\mid\operatorname{dist}_G(s,u)=i\}, \quad i=0,1,\ldots,d_{\max}.$$
2. 给出在 $O(|E|)$ 时间内计算所有 $\{\sigma_G(s,u)\mid u\in V\}$ 的方法。
3. 对给定的 $t\in V\setminus\{s\}$ 和 $A\subseteq V\setminus\{s,t\}$，在 $O(|E|)$ 时间内计算从 $s$ 到 $t$ 且至少经过一个 $A$ 中顶点的最短路条数。
4. 对同样的 $t,A$，在 $O(|E|)$ 时间内判定是否存在从 $s$ 到 $t$ 且至少经过两个 $A$ 中顶点的最短路。

Kai

Almost the same as 京都大学 情報学研究科 数理工学専攻 2024年8月実施 グラフ理論, please check it.

(i) 与えられた木を使う点

$T$ を根 $s$ から深さ優先探索または幅優先探索し、各頂点の深さを記録する。 $T$ は $G$ の幅優先探索木なので、この深さは $\operatorname{dist}_G(s,u)$ に等しい。 深さごとに頂点をリストに入れ、最大の深さを求めればよい。 木の辺数は $|V|-1$ なので、ここでは $G$ の全辺を再走査せず $O(|V|)$ 時間となる。

(ii)–(iv) 本問への適用

(ii) は上記リンクの層ごとの最短路数の漸化式を使う。 (iii) では距離が $1$ 増える辺だけを使い、$A$ の頂点への遷移を禁止して数えた経路数を 全最短路数から引く。「$A$ を削除したグラフの最短路」を数えると、元の最短距離より長い経路を含み得るので、元の層を維持する。 (iv) は各頂点までの最短路上で通る $A$ の頂点数の最大値を動的計画法で求め、終点で $2$ 以上かを判定する。 どちらも辺を高々定数回調べるので $O(|V|+|E|)=O(|E|)$ 時間である（$|V|\ge2$）。 経路数の加算を定数時間とする計算モデルを用いる。