Euler trail・circuit
概要
全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。
考え方
現在地から未使用辺を進み、行き止まりで頂点を逆順に出力するHierholzer法を使う。途中のcycleを元のwalkへ挿入することで、次数条件を満たす全辺を一つの列に組み込める。
stackに始点を入れ、各頂点に未走査隣接辺のcursorを持つ。末尾vに未使用辺eがあればIDを使用済みにし、行き先と進入辺IDをpushする。なければvをpopして答えの末尾へ加える。使用済み辺はcursorで読み飛ばし、最後に答えを逆順へ戻す。辺列が必要ならpop時に進入辺IDも保存する。辺ごとのcursor進行とpush・popは一回ずつなので線形時間。
trailの始点は無向なら奇数次数頂点、有向なら出次数−入次数=1の頂点。circuitなら辺を持つ任意頂点にする。E=0は指定始点だけの長さ0の列を返す。次数条件を満たしても別成分の辺を残す場合があるので、辺を持つ部分の連結性または使用辺数Eを確認する。行き止まりから逆順に足す操作が、完成した小cycleを残りのwalkへ挿入することに対応する。
成立条件と計算量
辺IDと各頂点の走査位置を持てばO(V+E)。無向辺は二方向の隣接情報を同じIDで管理し、parallel edgeを区別する。出力長がE+1かを検査し、開始頂点を奇数次数や入出次数差から選ぶ。
問題一覧
- ABC286 G「Unique Walk」 公式問題組合せ: DSUによる連結成分管理・縮約
技能・出典
主題: Euler trail・circuit(無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Euler trail・circuit / 補助タグ: DSUによる連結成分管理・縮約
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC227 H「Eat Them All」 公式問題主題: 最大流・最小カット
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: Euler trail・circuit(全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: Euler trail・circuit、最大流・最小カット / 補助タグ: 有界全列挙・有限case分解
- ABC336 G「16 Integers」 公式問題
技能・出典
主題: BEST定理によるEuler circuit数え上げ(有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: Euler trail・circuit(無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: BEST定理によるEuler circuit数え上げ / 補助タグ: 組合せ係数・数え上げ、行列式による数え上げ、Euler trail・circuit、法上の四則演算・高速累乗・逆元
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。次数条件を理解し、辺を一度ずつ使うHierholzer法を実装する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 次数parityからwalkや選択辺集合を判定・構成する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-euler-trail-circuit
Euler trail・circuit
習得する技能
- 無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。
- 全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 指定次数parityの部分グラフ構成、BEST定理によるEuler circuit数え上げ。
全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- Euler trail・circuitの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。