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

标签：

• Kyoto-University
• Shortest-Path-Problem

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|)$ 時間で計算する方法を示せ。

Kai

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