理論計算機科学を読むための数学・証明・アルゴリズム基礎

第6章 グラフと木

章間ナビゲーション

この章で使う記号

記号 意味
G = (V, E) 頂点集合 V と辺集合 E からなるグラフ
deg(v) 頂点 v の次数
u ↝ v u から v へ到達可能であることを表す記法
d(s, v) 始点 s から v までの距離
T 木を表すことが多い記号
DAG 有向非巡回グラフ

この章で解消する詰まりどころ

グラフは、状態遷移、到達可能性、ネットワーク、依存関係、オートマトン、証明構造、並行計算のモデルなど、理論計算機科学の多くの場所で使われます。

この章では、次を扱います。

  • 無向グラフ
  • 有向グラフ
  • パス、閉路
  • 連結性
  • 木
  • DAG
  • 到達可能性
  • BFS
  • DFS
  • トポロジカルソート

本体教科書のどこで使うか

  • 第3章 形式言語とオートマトン理論
  • 第7章 データ構造の理論
  • 第8章 グラフ理論とネットワーク
  • 第12章 並行計算の理論

1. 無向グラフ

無向グラフ G は、頂点集合 V と辺集合 E の組です。

G = (V, E)

無向グラフでは、辺は向きを持ちません。辺 {u,v} は u と v を結びます。

2. 有向グラフ

有向グラフでは、辺に向きがあります。

E ⊆ V × V

辺 (u,v) は、u から v への辺を表します。

有向グラフは、状態遷移や依存関係を表すときに使います。

3. 次数

無向グラフで、頂点に接続する辺の本数を次数と呼びます。

有向グラフでは、

  • 入次数: 頂点に入る辺の本数
  • 出次数: 頂点から出る辺の本数

を区別します。

4. パスと閉路

パスとは、辺に沿って頂点をたどる列です。

v0, v1, ..., vk

各 i について、vi と v{i+1} の間に辺があれば、これはパスです。

閉路とは、始点と終点が同じパスです。

5. 連結性

無向グラフが連結であるとは、任意の2頂点の間にパスが存在することです。

有向グラフでは、向きを考慮した到達可能性を使います。

6. 木

木は、連結で閉路を持たない無向グラフです。

木には、次の同値な特徴があります。

  • 連結で閉路を持たない。
  • 任意の2頂点の間に単純パスがちょうど1つ存在する。
  • n 頂点なら辺数は n-1。
  • 閉路を作らずに辺を追加できない。
  • 連結性を失わずに辺を削除できない。

7. DAG

DAG は Directed Acyclic Graph の略で、有向閉路を持たない有向グラフです。

DAG は、依存関係を表すのに適しています。

例:

  • タスク依存関係
  • コンパイル依存関係
  • 証明の依存関係
  • 計算グラフ

8. 到達可能性

有向グラフで、頂点 u から辺の向きに従って頂点 v へ進めるとき、v は u から到達可能であると言います。

到達可能性は、辺関係の反射推移閉包として見られます。

9. BFS

BFS は Breadth-First Search、幅優先探索です。

開始頂点から距離が近い順に探索します。キューを使います。

BFS(G, s):
    for each v in V:
        visited[v] = false
    visited[s] = true
    Q = empty queue
    enqueue(Q, s)

    while Q is not empty:
        u = dequeue(Q)
        for each v in Adj[u]:
            if not visited[v]:
                visited[v] = true
                enqueue(Q, v)

BFS は、無重みグラフの最短距離を求めるときにも使えます。

10. DFS

DFS は Depth-First Search、深さ優先探索です。

進めるところまで深く進み、行き止まりになったら戻ります。再帰またはスタックで実装できます。

DFS-VISIT(u):
    visited[u] = true
    for each v in Adj[u]:
        if not visited[v]:
            DFS-VISIT(v)

DFS は、連結成分、閉路検出、トポロジカルソートなどで使われます。

11. トポロジカルソート

DAG の頂点を、すべての有向辺 (u,v) について u が v より前に来るように並べることをトポロジカルソートと呼びます。

トポロジカルソートが可能であるための条件は、グラフがDAGであることです。

12. 非例・誤解しやすい例

誤解1: グラフは図であり、集合ではない

図は直観を助ける表現です。数学的には、グラフは頂点集合と辺集合で定義されます。

誤解2: BFS と DFS は同じ順序で探索する

どちらも到達可能な頂点を探索できますが、訪問順序と用途が違います。

誤解3: 有向グラフで u から v に到達できれば、v から u にも到達できる

有向辺には向きがあります。逆方向に進めるとは限りません。

13. 接続問題

有限オートマトンは、状態を頂点、遷移を有向辺と見ることができます。

また、並行計算の状態遷移システムも有向グラフとして扱えます。頂点は状態、辺は状態遷移です。

演習

Level 1

  1. 無向グラフと有向グラフの定義を書け。
  2. パスと閉路の違いを説明せよ。
  3. 木の定義を1つ書け。
  4. DAG の定義を書け。

Level 2

  1. n 頂点の木の辺数を答えよ。
  2. BFS と DFS の違いを説明せよ。
  3. 有向グラフの到達可能性を説明せよ。
  4. トポロジカルソートが可能な条件を述べよ。

Level 3

  1. n 頂点の木の辺数が n-1 であることを証明せよ。
  2. 有向グラフの到達可能性関係が推移的であることを証明せよ。
  3. DAG には入次数0の頂点が少なくとも1つ存在することを証明せよ。
  4. BFS が無重みグラフで最短距離を求める理由を説明せよ。

自己診断

次を満たせば、この章は通過です。

  • グラフを集合として定義できる。
  • 木の基本性質を説明できる。
  • BFS と DFS の擬似コードを読める。
  • 到達可能性を関係として説明できる。
  • DAG とトポロジカルソートの関係を説明できる。

次に読む章

Edit this page on GitHub