指定次数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へ移した構成であり、厳密な次数指定や辺数最小化は別問題になる。

問題一覧

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

前提・学習成果・出典

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

根拠