単一サイクル成分とgraph core

概要

連結成分の辺数と頂点数が等しいとき、その成分は一つの閉路と、閉路の各頂点に付く木へ分かれる。葉を剥がして閉路を取り出すと、木の部分と閉路の部分で、辺の向きや経路の選び方を分けて考えられる。

辺数から単一cycleを読む

連結な単純無向グラフの頂点数を VV、辺数を EE とする。親単元で導いた cycle rankは E−V+1E-V+1 なので、E=VE=V なら全域木に足す辺は一本だけである。その一辺と木の中の経路が唯一の閉路を作り、他の頂点は閉路上の各頂点へ木として付く。枝が別の閉路を作ったり、閉路の二か所につながったりすれば、さらに閉路ができるためである。

連結なら E≥V−1E\geq V-1 なので、E<VE<V の場合は E=V−1E=V-1、つまり木である。E>VE>V なら独立な閉路が複数あり、以降の単一閉路を仮定する議論は使えない。ABC226 Eでは成分ごとに E=VE=V を調べ、ABC266 Fではこの条件が保証されたグラフから実際に閉路を取り出す。

考え方

三角形に付いた枝を剥がす

独自例として、三角形 1–2–3–1 に枝 3–4–5 を付ける。辺は {1,2},{2,3},{3,1},{3,4},{4,5}\{1,2\},\{2,3\},\{3,1\},\{3,4\},\{4,5\} の5本なので、V=E=5V=E=5、cycle rank は1である。

葉刈りでは、各頂点の未削除頂点への辺数を現在次数 deg[v] として持つ。初めに次数1以下の頂点を全てキューへ入れる。取り出した頂点が削除済みなら飛ばし、そうでなければ削除済みにする。その未削除隣接頂点の次数を減らし、次数が2から1へ下がった時点で新しくキューへ入れる。既にキューにある頂点が後から次数0になっても、再登録は不要である。

この例の更新は次のようになる。

  1. 初期化する。 頂点1から5の次数は順に (2,2,3,2,1)(2,2,3,2,1)。5をキューへ入れる。残る頂点は {1,2,3,4,5}\{1,2,3,4,5\}。
  2. 5を削除する。 4の次数が2から1へ下がるので、ここで4を入れる。残る頂点は {1,2,3,4}\{1,2,3,4\}。
  3. 4を削除する。 3の次数は3から2へ下がる。削除対象にはならない。残る頂点は {1,2,3}\{1,2,3\}。

キューが空になり、三角形だけが残る。閉路上の頂点は閉路内の二辺を失わないので消えず、外側の枝は有限の木なので葉から全て消える。親単元の不変量から、他の例で削除できる葉が複数あっても、どの順に処理するかで最終的な2-coreは変わらない。

削除順から枝の根を復元する

単一閉路の成分では、枝の頂点を削除するとき、未削除の隣接頂点は一つだけである。それを閉路側の親 parent[v] として保存する。上の例では削除順は5、4で、parent[5]=4、parent[4]=3 となる。

次に、残った閉路の各頂点に自分自身を根ラベル root[v] として付ける。削除順を逆にたどり、root[v]=root[parent[v]] とすれば、親のラベルは既に決まっている。例では4へ3を、次に5へ3を渡し、最終的なラベルは頂点1から順に (1,2,3,3,3)(1,2,3,3,3) となる。閉路の辺を使わず、各閉路頂点から枝へ探索しても同じラベルが得られる。

向き付けと一意な経路へ使う

ABC226 E は、各頂点から出る辺をちょうど一本にする向き付けを数える。成分内の出次数を足すと頂点数になり、一方で各辺は出次数に一度ずつ寄与するため、まず E=VE=V が必要になる。例の葉5は 5→45\to4、次の葉4は 4→34\to3 に向けるしかない。こうして枝の向きは閉路へ向かう方向に強制され、残る三角形は一周する二方向のどちらでも条件を満たす。各成分が独立なので、成分数を CC とすると、全成分で E=VE=V なら答えは 2C2^C、一つでも不一致なら0となる。実装では成分ごとの頂点数と辺数を数えるだけでよく、葉刈り自体は不要である。

ABC266 F は、二頂点間の単純パス、つまり同じ頂点を二度通らない経路が一意かを問う。同じ根ラベルの頂点は一つの木に属し、その中の経路は一意である。閉路へ寄り道して戻るには同じ根を再訪するため、別の単純パスにはならない。異なる根ラベルなら、それぞれの根の間で閉路を回る二方向が選べる。従って根ラベルの一致だけで判定できる。

例では4と5の根は共に3で、経路は 4–5 の一本だけである。一方、5と1の根は異なり、5–4–3–1 と 5–4–3–2–1 の二本がある。閉路頂点3自身と5のような組も、同じラベル比較で扱える。

複数の閉路があるときに残るもの

別々の三角形 u–a–b–u と v–c–d–v を、新しい頂点 xx を挟んだ長さ2の経路 u–x–v で結ぶ。このグラフは7頂点8辺、cycle rank は2である。u,vu,v の次数は3、それ以外の5頂点の次数は2なので、キューは最初から空で7頂点全てが2-coreに残る。

しかし u–x と x–v は、取り除くとグラフが分断される辺、すなわち橋である。xx を通る単純閉路を作ろうとしても、二つの三角形の間には他の経路がなく、同じ橋を戻るしかない。従って xx はどの単純閉路上にもない。残存頂点がちょうど閉路上の頂点になることも、各頂点を唯一の閉路根へ割り当てられることも、単一閉路という仮定に依存する。

成立条件と計算量

グラフ全体の頂点数・辺数を改めて V,EV,E とする。隣接リストの構築、成分の探索、次数の初期化、葉刈り、根ラベルの復元は、各頂点・各辺を定数回処理するので時間 O(V+E)O(V+E)。隣接リスト・現在次数・削除済みフラグ・キュー・親・削除順・根ラベルを含め、空間も O(V+E)O(V+E) である。問い合わせが QQ 個なら、ラベルの一致判定は一回 O(1)O(1)、全体で O(V+E+Q)O(V+E+Q) 時間となり、問い合わせを順に読んで答えれば保存用の追加空間は不要である。

木は E=V−1E=V-1 で、葉を剥がすと全頂点が消える。孤立点も初期次数0として削除する。例えば三角形と一本の辺と孤立点が別々の成分なら、2-coreには三角形だけが残る。この場合、木の最後の頂点には未削除の親がなく、閉路根ラベルも付けられない。一般の2-coreを求める手順と、単一閉路の成分で親・根ラベルを使う手順を区別する。

非連結グラフの構造は成分ごとに確認する。全体で辺数と頂点数が等しくても、木の成分と複数閉路の成分が混ざり得るため、ABC226 Eの条件を全体の総数だけでは判定できない。自己ループや多重辺を許すかで閉路の表現が変わるので入力条件も確認する。ここで接続した二問はいずれも単純無向グラフであり、複数閉路の成分へ単一閉路の議論を拡張しない。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。成分のE−V+1から閉路数を読み、必要なら葉を剥がして残るcoreを調べる。

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

概念上の親: 閉路数・次数構造からgraph coreを調べる。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-graph-core

単一サイクル成分とgraph core

習得する技能

  • 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: near-tree graphのkernel化。

連結成分の辺数と頂点数からcycle rankを判定し、必要なら葉を反復削除してcycle coreと削除順を得る。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 単一サイクル成分とgraph coreの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠