跳到主要内容

京都大学 情報学研究科 数理工学専攻 2024年8月実施 グラフ理論

标签：

Author​

祭音Myyura

Description​

有限集合 に属する要素の個数を と書く。 節点集合 および枝集合 からなる単純連結無向グラフ が与えられたものとする。 ただし とする。 始点 を一つ選ぶ。 任意の節点 に対し、 から への最短路における枝の本数を と書き、 から への最短路の総数を と書く。 また、 とし、整数 に対して とする。以下の問いに答えよ。

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

(ii) すべての に対して を 時間で計算する方法を示せ。

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

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

Kai​

(i)​

dist[v] = -1
dist[s] = 0
V_0 = {s}
queue = [s]

while queue not empty:
    u = pop_front(queue)
    for v in N(u):
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            add v to V_{dist[v]}
            push_back(queue, v)

d_max = max dist[v]

Since graph is connected, we have . Hence the time complexity is .

(ii)​

sigma[v] = 0 for all v
sigma[s] = 1

for i = 0 to d_max - 1:
    for u in V_i:
        for v in N(u):
            if dist[v] == dist[u] + 1:
                sigma[v] += sigma[u]

(iii)​

a[v] = 0 for all v
a[s] = 1

for i = 0 to d_max - 1:
    for u in V_i:
        for v in N(u):
            if dist[v] == dist[u] + 1 and v not in U:
                a[v] += a[u]

return sigma[t] - a[t]

(iv)​

best[v] = -infinity for all v
best[s] = 0

for i = 0 to d_max - 1:
    for u in V_i:
        for v in N(u):
            if dist[v] == dist[u] + 1:
                gain = 1 if v in U else 0
                best[v] = max(best[v], best[u] + gain)

return best[t] >= k
目录