一意な後続・サイクル・ダブリング

概要

状態グラフを理解した後、後続が一意という制約からcycleと流入木への分解やダブリングを導く。

考え方

各頂点の行き先が一つなら、各成分は一つのcycleとそこへ流れ込む木になる。何回移動したかを扱う方法と、cycleへ着くまでの距離や周期を使う方法を比較する。

成立条件と計算量

明示的なN頂点なら構造分解はO(N)。巨大回数にはcycle長による剰余かbinary liftingを使う。出次数が一つであることが本質で、任意の有向graphへ同じ分解を適用しない。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。後続が一意な遷移をcycleと流入木に分け、反復を圧縮する入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-functional-graph

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 各頂点から複数の後続を選べる一般のグラフ探索・強連結成分への縮約。

根拠