跳到主要内容

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

Author​

祭音Myyura

Description​

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

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

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

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

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

Kai​

(i)​

Core idea: Use BFS starting from to calculate the shortest distance for all nodes .

Input: Graph G = (V, E), starting node s
Output: d_max, V_i for i = 0, 1, ..., d_max

dist[v] = -1 for all v in V
dist[s] = 0
d_max = 0
V_i = [] (an empty list for each layer)
queue = [s]

while queue is not empty:
    u = queue.pop(0)
    for each neighbor v of u:
        if dist[v] == -1:  # v is unvisited
            dist[v] = dist[u] + 1
            d_max = max(d_max, dist[v])
            queue.append(v)

            V_i[dist[v]].append(v)

return d_max and V_i

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

(ii)​

Core idea: To calculate , we can modify the standard BFS. While traversing the graph, keep track of the number of shortest paths reaching each node .

Input: Graph G = (V, E), starting node s
Output: sigma[v] for all v in V

dist[v] = -1 for all v in V
dist[s] = 0
sigma[v] = 0 for all v in V
queue = [s]

while queue is not empty:
    u = queue.pop(0)
    for each neighbor v of u:
        if dist[v] == -1:  # v is unvisited
            dist[v] = dist[u] + 1
            queue.append(v)
        if dist[v] == dist[u] + 1:  # shortest path to v passes through u
            sigma[v] += sigma[u]

return sigma[v] for all v

(iii)​

Core idea: If a node is in one of shortest -paths, then .

Input: Graph G = (V, E), source s, target t, subset U ⊆ V \ {s, t}
Output: Number of nodes in U that participate in any shortest path from s to t

dist_from_s[v] = ∞ for all v in V
Set dist_from_s[s] = 0
Perform BFS to compute dist_from_s[v] for all v in V

dist_to_t[v] = ∞ for all v in V
Set dist_to_t[t] = 0
Perform BFS to compute dist_to_t[v] for all v in V

participation_count = 0
for each u in U:
    if dist_from_s[u] + dist_to_t[u] == dist_from_s[t]:
        participation_count += 1

return participation_count

(iv)​

Core idea: Similar with (2), while traversing the graph, keep track of the number of nodes in encountered on the shortest paths reaching each node .

Input: Graph G = (V, E), source s, target t, subset U ⊆ V \ {s, t}, integer k
Output: True if there exists a shortest path from s to t with at least k nodes in U; otherwise False

dist = {v: ∞ for v ∈ V}  (Shortest distance to each node)
dist[s] = 0
queue = [(s, 0)]  (BFS queue: (node, count of nodes in U on path))
count = {v: -1 for v ∈ V}  (Tracks the max count of U nodes on shortest path to v)

While queue is not empty:
    Pop (u, u_count) from queue
    For each neighbor v of u:
        If dist[v] > dist[u] + 1:  (Found a shorter path to v)
            dist[v] = dist[u] + 1
            new_count = u_count + 1 if v ∈ U else u_count
            count[v] = new_count
            Push (v, new_count) into q
        Else if dist[v] == dist[u] + 1:  (Found another shortest path to v)
            new_count = u_count + 1 if v ∈ U else u_count
            If new_count > count[v]:  (Update count if this path has more nodes in U)
                count[v] = new_count
                Push (v, new_count) into q

If count[t] ≥ k, return True; otherwise, return False.
目录