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かを検査し、開始頂点を奇数次数や入出次数差から選ぶ。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠