京都大学 情報学研究科 数理工学専攻 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)