有向森の定義とアルゴリズム・応用を徹底解説：アービュレッセンスとポリツリーの違いから実践まで

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

はじめに — 「有向森」とは何か

有向森（ゆうこうもり、directed forest）は、グラフ理論やアルゴリズム設計、確率的モデルなど IT の多くの領域で現れる基本概念です。一見すると「森（複数の木）」に向き（有向辺）を付けただけに見えますが、文脈により若干意味合いが異なるため、本稿では定義の整理、基本的性質、判定や生成アルゴリズム、関連する概念（有向木／アービュレッセンス、ポリツリー、DAG 等）との違い、応用例まで詳しく掘り下げます。

定義の整理

まず、「有向森」という語には主に次の 2 種類の使われ方があります。文献や分野によって使い方が異なるので注意が必要です。

  • （A）アービュレッセンス群としての有向森：各弱連結成分（undirected に見たときの連結成分）が「有向根付き木（arborescence）」であるような有向グラフ。一般に各頂点の入次数が最大 1（根を除く各頂点の入次数がちょうど 1）であり、方向付きの根付き木が複数並んだものと理解できます。親ポインタ方式で表されるツリー群（典型的にはファイルツリーや親配列での表現）に対応します。
  • （B）森の向きづけ（各無向森を任意に向けたもの）としての有向森（ポリツリー／オリエンテッドフォレストに近い概念）：基礎となる無向グラフが森であり、その辺に任意の向きを付けたもの。各弱連結成分の基底は無向木なので、有向化しても有向サイクルは生じません（無向サイクルが存在しないため）。この定義の下では、ある頂点の入次数が 2 以上になることも許されます（親が複数いるような向きづけが可能）。単一成分の場合は「ポリツリー（polytree）」と呼ばれます。

多くのプログラミング・システムやデータ構造（親ポインタで表される森林）では（A）の意味で使われることが多く、確率的グラフィカルモデル（ベイズネット）などでは（B）の「ポリツリー」の概念が多用されます。以下では両者の違いを明確にしつつ議論を進めます。

基本的性質

有向森（上のどちらの定義を取るにせよ）には次のような基本性質があります。

  • 無向グラフとしての基底が森であるため、辺と頂点の関係が m = n - c（m：辺数、n：頂点数、c：弱連結成分数）を満たします。特に各成分が木ならば各成分で頂点数 k に対して辺数は k - 1 です。
  • 有向サイクルは存在しません（有向サイクルが存在すると、その無向バージョンもサイクルとなるため）。したがってトポロジカルソートが可能です（DAG の性質）。
  • （A）の定義を採るとき、各頂点の入次数は最大 1。根は入次数 0 であり、その他は入次数 1 である。従って各成分における「根」の存在が自然に定まります。
  • （B）の定義（ポリツリー）では入次数は頂点の元の無向次数に依存し、1 を超えることがあるが、依然として有向サイクルは生じない。
  • 任意の有向森は必ず DAG（有向非巡回グラフ）であり、深さ優先や幅優先で木構造の走査が可能です。

有向森を判定・生成するアルゴリズム

実用上、与えられた有向グラフが有向森に該当するかを判定したり、ある無向森林を有向化したり、最小コストでアービュレッセンスを求めたりする処理が求められます。代表的な方法を示します。

判定（グラフが有向森か）

  • 方法 1（基底が森かどうかを確認）：
    • 無向化して（各有向辺を無向辺として扱い）無向グラフが森か（サイクルがないか）を調べる。無向サイクルがなければ underlying graph は森。また辺数が n - c になっているかを確認する。
  • 方法 2（アービュレッセンス群としての判定）：
    • 全頂点の入次数を計算し、入次数がすべて ≤ 1 であることを確認する（入次数 1 のものは親が 1つ）。
    • さらに有向サイクルがないこと（トポロジカルソートや DFS による検出）を確認する。入次数 ≤1 かつサイクルなしであれば各弱成分はアービュレッセンスとなる。

計算量は辺数を E、頂点数を V とすると、入次数計算・無向化・DFS/トポロジカルソートいずれも O(V + E) で実行できます。

生成・最小アービュレッセンス（最小向きスパニングツリーの有向版）

  • ある重み付き有向グラフから「根付き最小アービュレッセンス（minimum spanning arborescence）」を見つける代表的アルゴリズムは Chu–Liu/Edmonds アルゴリズムです。計算量は実装によるが基本的には O(EV) 程度（最適化やデータ構造で改善可能）です。
  • また、ある頂点を根とする全ての有向スパニングアービュレッセンスの数を数えるには、有向版の Matrix‑Tree 定理（Directed Matrix‑Tree theorem）を使ってラプラシアンの小行列式（コファクター）を計算することで得られます。これには O(n^3) 程度の行列演算が必要です（ガウス消去等）。

関連する概念との対比

用語が多く混同されやすいので、代表的な概念との違いを整理します。

  • DAG（有向非巡回グラフ）：有向グラフで有向サイクルがないもの。DAG は非常に広いクラスであり、ポリツリーや有向森はその部分集合です。DAG は必ずしも underlying graph が森である必要はありません（多くの辺がある可能性があります）。
  • アービュレッセンス（arborescence）／有向木：根を持ち、根から任意の頂点へちょうど一つの有向パスがあるような有向根付き木。全ての非根頂点が入次数 1 で、根が入次数 0。アービュレッセンスの集合は（A）の意味の有向森を構成します。
  • ポリツリー（polytree）：underlying の無向グラフが木である DAG（単一成分のオリエンテッドフォレスト）。ベイズネットで「シングリー接続（singly connected）」な構造を表すときに用いられます。複数の親（入次数 >1）を持つノードが存在し得ますが、全体はサイクルを持ちません。
  • 機能的グラフ（functional graph）：各頂点の出次数がちょうど 1 である有向グラフ。こちらは定義上サイクル（1 個以上）を含むことが一般的で、そこにツリー状の枝が突き刺さる構造（サイクル＋木）が現れます。アービュレッセンス群とは逆の条件（出次数 1）なので混同しないよう注意。

有向森の応用例（IT における具体例）

  • データ構造：親配列で表現される複数のルートを持つ木集合（例えばファイルシステムの部分集合、組織図の分岐など）。操作（根の探索、深さ・高さの計算、祖先クエリ）は木アルゴリズムで扱える。
  • Union‑Find（Disjoint Set）実装：集合を木（親ポインタ）で表す際、一連の親ポインタが森林を形成します（経路圧縮によって木の形は変化する）。
  • 確率的グラフィカルモデル：ベイズネットの一形態としてポリツリー構造は、信念伝播（belief propagation）により効率的かつ厳密な推論が可能です。ポリツリーは単一の無向木を向きづけたもので、連鎖確率や条件付き独立性の表現が簡素です。
  • ネットワーク設計・ルーティング：ルートからの一方向のツリー状配布（放送木／ブロードキャストツリー）や、センシングネットワークでの集約木（データを根に集める）など。
  • 最小有向スパニング木問題（最小アービュレッセンス）：有向グラフ上で特定の根に全頂点を到達させる最小コストの枝集合を求める問題は、Chu–Liu/Edmonds アルゴリズムで解きます。これは通信ネットワークや配布ネットワークの設計に使われます。

例：簡単な有向森の見分け方（手順）

例えば、ある有向グラフが与えられたときにそれが「親ポインタ型森林」（各頂点の入次数 ≤ 1 かつサイクルなし）であるかを判定する簡単な手順：

  • 全頂点について入次数をカウントする。もし入次数が 2 以上の頂点があれば（A の意味の）有向森林ではない。
  • トポロジカルソートを試みる（Kahn のアルゴリズムなど）。ソートに失敗して有向サイクルが発見されたら森林ではない。
  • 上の 2 点を満たすならば、各弱成分は根からの有向木（アービュレッセンス）になっている。

理論的トピック（マトリックスツリー定理、最小アービュレッセンス等）

有向グラフのスパニングアービュレッセンスに関する深い理論も存在します。主要なものを簡潔に紹介します。

  • 有向版 Matrix‑Tree 定理：有向グラフにおいて、ある頂点 r を根とする spanning arborescences の個数は、対応するラプラシアン類似行列（out-degree を対角に置き、i→j の辺の数を負で置くような行列）の r 行・r 列を削った小行列式（コファクター）で与えられます。行列式計算は一般に O(n^3)（ガウス消去）です。この定理によりアービュレッセンスの個数を効率的に数えることができます。
  • Chu–Liu / Edmonds のアルゴリズム：有向グラフから根付き最小コストアービュレッセンスを求めるアルゴリズム。基本版の計算量は O(EV) とされ、実装とデータ構造で改善できます。ネットワークの最小配布木や分散システムの最適設計で利用されます。

実装上の注意点・落とし穴

  • 「有向森」という語の曖昧さ：文脈により（A）または（B）の意味で使われることがあるため、仕様書や設計書では「各頂点の入次数が最大 1 か」「基底が無向森か」どちらの意味か明記すること。
  • 入次数だけでの判定は注意が必要：入次数 ≤ 1 でも有向サイクルを持つ（理論上は無いはずだが確認のためトポロジカルソートは行う）ケースや、期待する根の数と一致しないケースに注意。
  • 重み付き最小アービュレッセンスを求める場合はアルゴリズムの選定（Chu–Liu/Edmonds 等）と実装上の数値安定性に注意。

まとめ（実務での取り扱い方）

有向森は「木（forest）に向きを与えたもの」という直感から発展する概念で、親ポインタで表される実用的な森林（アービュレッセンス群）と、無向木の任意向き付け（ポリツリー）という二つの使われ方があります。どちらも有向サイクルを持たない点で共通し、トポロジカルソートや深さ優先/幅優先探索で効率的に扱えることが利点です。応用はデータ構造、ネットワーク設計、確率モデルなど幅広く、理論的には Matrix‑Tree 定理や Chu–Liu/Edmonds アルゴリズムといった強力な道具が用意されています。

参考文献

カテゴリー
IT
前の記事
部分順序グラフの基礎から実務応用まで：DAG・Hasse図・トポロジカルソート・トランジティブリダクションを徹底解説New!!
2025年11月20日
次の記事
BFS（幅優先探索）入門：最短経路・連結成分・二部グラフ判定まで網羅する実践ガイドNew!!
2025年11月20日