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

Author

祭音Myyura

Description

を節点集合 、枝集合 から成る連結な単純無向グラフとし、節点 の隣接の集合を と書く。 の部分グラフ における節点 から節点 への最短路内の枝数を と書き、 における節点 から節点 への最短路の総数を と書く。 始点 を選び、 を からの幅優先探索により得られた の全域木とする。 以下の問いに答えよ。

(i) を用いて、 および , を 時間で計算する方法を示せ。

(ii) 内のすべての値を 時間で計算する方法を示せ。

(iii) ある節点 と節点の部分集合 に対して、 における から への最短路のうち、 の節点を１個は通過するものの個数を 時間で計算する方法を示せ。

(iv) ある節点 と節点の部分集合 に対して、 における から への最短路のうち、 の節点を少なくとも２個通過するものが存在するかどうかの判定を 時間で計算する方法を示せ。

Kai

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