指定次数parityの部分グラフ構成
概要
選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。
考え方
選んだ辺の次数偶奇を指定するとき、木の葉から残りの要求を処理する。子の要求が奇なら親辺を選んで両端を反転し、子の条件を確定する。
要求bit need[v]を「指定した次数偶奇」として初期化し、全成分の探索森とpostorderを作る。根以外のvを子から順に読み、need[v]=1なら親辺を採用してneed[v]とneed[parent[v]]を反転する。0なら親辺を採用しない。処理済みの子孫はもう辺を変えず、needは現在の次数と目標のXOR差を表すので、vを処理した後はその全条件が確定する。
一辺は二端点のbitを反転するため、成分全体のneedのXORは変わらない。最後の根のneedは初期要求の成分XORに等しく、0なら全要求を満たす構成、1ならどの辺集合でも実現不能である。採用した親辺のIDを返せばよい。孤立点は自身の要求が0のときだけ可能で、別成分の奇数要求同士を打ち消してもつなぐ辺は存在しない。
成立条件と計算量
成分ごとの要求偶奇の総XORが0なら構成可能で、探索木上でO(V+E)。根には親辺がないため最後に要求0を確認する。値をmod 2へ移した構成であり、厳密な次数指定や辺数最小化は別問題になる。
問題一覧
- ABC345 F「Many Lamps」 公式問題組合せ: 成立証明から構成解を復元する
技能・出典
主題: 指定次数parityの部分グラフ構成(選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 指定次数parityの部分グラフ構成 / 補助タグ: 構成解・witness復元
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。木の葉から奇偶条件を確定し、指定した奇数次数集合を実現する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 次数parityからwalkや選択辺集合を判定・構成する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-degree-parity-subgraph
指定次数parityの部分グラフ構成
習得する技能
- 選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: Euler trail・circuit。
このUnitを直接前提とする単元: なし。
Euler trail・circuitで得た考え方と実装を再利用し、指定次数parityの部分グラフ構成の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 指定次数parityの部分グラフ構成の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。