跳到主要内容

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

Author​

祭音Myyura

Description​

日本語版​

を点集合 ，枝集合 から成る単純有向グラフとする． を において点 から有向路で到達できる点の集合と定め， を点 から点 へ至る の有向路の最短の長さとする． のときは と定める． 有向グラフ から有向枝 を削除した有向グラフを と記す． を の二点とする． は隣接リストにより貯えられているとする．以下の問いに答えよ．

(i) と仮定する． 点 から点 へ至る有向路で最短のものを求める 時間アルゴリズムを与えよ．

(ii) を満たす有向枝 が存在するかどうかを判定する 時間アルゴリズムを与えよ．

(iii) である二点 有向枝 をもつ有向グラフ の例を作成せよ．

English Version​

Let be a simple directed graph with a vertex set and an edge set . Let denote the set of vertices reachable from a vertex by a directed path in and denote the shortest length of a path from a vertex to a vertex in , where we set if . Let denote the directed graph obtained from by removing a directed edge . Let and be two vertices in . Assume that is stored in adjacency lists. Answer the following questions.

(i) Assume that . Give an -time algorithm that computes a directed path with the shortest length from to .

(ii) Give an -time algorithm that tests whether there exists a directed edge such that .

(iii) Construct an example of a directed graph that contains two vertices and a directed edge such that .

Kai​

(i)​

We use BFS to compute shortest paths in an unweighted graph.

BFS(s, G=(V, E)):
    for each v in V set dist(s, v; G) = |V|
    for each v in V set visited(v) = 0
    for each v in V set pred(v) = -1
    dist(s) = 0
    visited(s) = 1
    set Q to be the empty queue
    Q.enqueue(s)
    while Q is not empty do:
        u = Q.dequeue()
        for each neighbor v of u do:
            if visited(v) = 0 then:
                visited(v) = 1
                Q.enqueue(v)
                dist(s, v; G) = dist(s, u; G) + 1
                pred(v) = u

The time complexity of BFS is when is stored in adjacency lists.

(ii)​

The idea is to find "bridges" in the graph that consists of all the edges of shortest paths from to .

Let denote the edge set of all the edges of shortest paths from to . To find , we do the following steps:

  • use BFS to compute
  • let denote the reversed graph of (i.e. the same vertex set but all of the edges reversed), use BFS to compute

Obviously, it takes -time to find the edge set .

Then, we can use Tarjan' algorithm to find bridges

GetArticulationPoints(i, d)
    visited[i] := true
    depth[i] := d
    low[i] := d
    childCount := 0
    isArticulation := false

    for each ni in adj[i] do
        if not visited[ni] then
            parent[ni] := i
            GetArticulationPoints(ni, d + 1)
            childCount := childCount + 1
            if low[ni] ≥ depth[i] then
                isArticulation := true
            low[i] := Min (low[i], low[ni])
        else if ni ≠ parent[i] then
            low[i] := Min (low[i], depth[ni])
    if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
        Output i as articulation point

The time complexity of Tarjan' algorithm is also

If there exists a articulation point in graph , i.e., there exists a bridge (adjacent to ) in , then the removal of disconnects , which implies that there is no path of length in , i.e.

(iii)​

目录