跳到主要内容

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

标签：

Author​

祭音Myyura

Description​

頂点集合 ,枝集合Aを持つ有向グラフ が与えられたものとする． に属する頂点の個数を , に属する枝の本数を とする． 任意の2頂点 について，から への有向路が存在するとき， とする．以下の問いに答えよ．

(1) に有向閉路が存在するか否かを 時間で判定する手順を示せ．

(2) 以下の (a),(b),(c) の各条件について， がその条件を満たすか否かを 時 間で判定する手順をそれぞれ示せ．

  • (a) どの2頂点 についても， と の高々一方が成り立つ．
  • (b) どの2頂点 についても， と の両方が成り立つ．
  • (c) どの2頂点 についても， と の少なくとも一方 が成り立つ．

Kai​

(i)​

Use depth-first search with three colors.

Each vertex is colored as follows:

  • white: not yet discovered;
  • gray: discovered but not finished, so it is currently in the DFS recursion stack;
  • black: finished.

The algorithm is as follows.

for each vertex v in V:
    color[v] = white

for each vertex v in V:
    if color[v] = white:
        DFS(v)

DFS(u):
    color[u] = gray
    for each arc u -> v:
        if color[v] = gray:
            report "there is a directed cycle"
        if color[v] = white:
            DFS(v)
    color[u] = black

The running time is , since every vertex is visited once and every arc is examined once.

To prove correctness, first suppose that DFS finds an arc such that is gray. Since is gray, is an ancestor of in the current DFS recursion stack. Hence there is already a directed path . Together with the arc , this gives a directed cycle.

Conversely, suppose that contains a directed cycle

Let be the first vertex on this cycle discovered by DFS. At that moment, all other vertices on the cycle are still white. Before becomes black, DFS explores all vertices reachable from , in particular the rest of the cycle. Thus DFS eventually reaches the predecessor of on the cycle and then examines the arc back to , while is still gray. Therefore DFS finds an arc to a gray vertex.

(ii)​

(a)​

The condition is equivalent to the following

The remaining directed graph has no directed cycle.

Indeed, if there is a directed cycle containing at least two distinct vertices, then any two vertices on the cycle are mutually reachable, contradicting the condition. Conversely, if two distinct vertices and are mutually reachable, then a path from to together with a path from to forms a directed cycle containing at least two distinct vertices.

Therefore, we may apply the algorithm from part (i). If the remaining graph is acyclic, condition (a) holds; otherwise it does not. The running time is .

(b)​

Tarjan's algorithm

(c)​

Let the strongly connected components of be

Contract each strongly connected component into one vertex. The resulting graph is called the condensation graph of . It is always a DAG.

Algorithm:

  1. Compute the strongly connected components of .

  2. Construct the condensation graph .

  3. Compute a topological ordering of :

  4. For each , check whether contains the arc

  5. If all such arcs exist, output true. Otherwise, output false.

To implement step 4 in linear time, mark all arcs of in a hash set or Boolean table indexed by component numbers. Equivalently, when scanning all arcs of , record the arcs between different components. Since each original arc is scanned only a constant number of times, the total running time remains .

Now we prove correctness.

First suppose that the algorithm outputs true. Then for every consecutive pair in the topological ordering, there is an arc

Hence for any , there is a directed path

Therefore every pair of components is comparable by reachability. Since vertices inside the same strongly connected component are mutually reachable, for any two vertices , at least one of and holds.

Conversely, suppose that satisfies the condition. Then any two strongly connected components of are comparable by reachability in the condensation graph . Take a topological ordering

of . For each consecutive pair , the topological order forbids a path from to . Hence, by the assumed condition, there must be a path from to . Since and are consecutive in a topological ordering, this path cannot pass through any other component. Therefore the path must be a single arc

Thus the algorithm will output true.

The running time is , because SCC computation, condensation graph construction, topological sorting, and the final scan are all linear.

目录