次数parityからwalkや選択辺集合を判定・構成する

概要

グラフを探索できることを前提に、全辺walkの成立性や選択辺集合の端点条件を次数parityで特徴付け、葉から判定・構成する。

考え方

全辺を一度ずつ通るwalkでは、内部頂点の到着と出発が対応する。無向なら奇数次数が0または2、有向なら入出次数差が端点だけに現れることが必要条件になる。

成立条件と計算量

次数集計O(V+E)に加え、辺を持つ頂点の適切な連結性を確認する。次数条件だけでは別成分を一つのwalkで通れない。辺が0本の規約、自己loopが次数へ与える寄与も固定する。

下位単元

問題一覧

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

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。次数と連結性から全辺を使う歩道や選択辺集合の条件を読む入口。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-euler-degree

前提と範囲

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

直接の前提単元: なし。

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

このUnitでは扱わないもの

  • 容量付きフロー・マッチング・最小カットへの帰着。

根拠