閉路数・次数構造からgraph coreを調べる
概要
辺数を数えると、連結成分が木からどれだけ離れているかが分かる。一方、次数の小さい頂点を反復削除すると、指定した次数条件を満たす核(core)が残る。この二つを組み合わせ、閉路が一つだけの成分を扱うのが単一サイクル成分とgraph coreである。
考え方
全域木から余る辺を数える
ここでは単純無向グラフを考える。一つの連結成分の頂点数を 、辺数を とする。この成分の全頂点を閉路なしでつなぐ全域木は 辺なので、木に使わない辺は
本ある。木にそのうちの一辺を足すと、その両端を結ぶ木の一意な経路と合わせて閉路ができる。各閉路には対応する非木辺が一つずつあり、その非木辺は他の閉路には含まれない。このように独立に加わる閉路の自由度 を cycle rank と呼ぶ。
これは単純閉路の総数ではない。例えば正方形に対角線を一本足すと で rank は2だが、単純閉路は二つの三角形と外周の正方形の計3個ある。非連結グラフ全体では、連結成分数を として rank は になる。閉路を組み合わせる意味と基底の証明はcycle space・fundamental cycle basisで扱う。
次数条件を満たせない頂点を剥がす
頂点集合を選び、その頂点間に元からある辺を全て残したものを誘導部分グラフという。その中で各頂点の次数が 以上になる、頂点集合が最大のものを k-core と呼ぶ。求めるには、現在の次数が 未満の頂点を反復して除く。除去により隣接頂点の次数も下がるので、最初の次数だけで一度に判定してはいけない。
この削除で目的の頂点を失わない理由を考える。それまでの削除で、条件を満たすどの誘導部分グラフの頂点も失っていないとする。現在次数が 未満の頂点は、残存頂点の一部だけを選んでも次数を増やせないため、そのどれにも属せない。従って次の削除も安全である。停止時には残存頂点の次数が全て 以上であり、条件を満たす全ての誘導部分グラフを含む。これが最大の k-core で、削除順によらず同じ頂点集合になる。
特に では次数1の葉と次数0の孤立点を除く。三角形 1–2–3–1 に枝 3–4–5 を付けると、最初は5だけが削除対象で、5を除いて初めて4の次数が1になる。次に4を除くと三角形が残る。三角形の頂点は内部に二辺ずつ持つので、上の不変量の通り一度も削除されない。現在次数の更新と、この残存集合を問題へ使う方法は下位単元で追う。
成立条件と計算量
削除対象をキュー(queue)で管理し、隣接リストと現在次数を使う。初めに次数が 未満の頂点を全て入れ、削除のたびに未削除の隣接頂点の次数を減らす。新しく閾値を下回った頂点を入れれば、各頂点を一度、各隣接辺を高々二度調べるので、時間・空間ともに である。ここでの は処理するグラフ全体の頂点数・辺数とする。
木や孤立点の2-coreは空になる。非連結なら各成分で同じ操作が独立に進み、閉路を持つ成分だけが残ることもある。coreが空か、連結か、独立な閉路がいくつあるかは別の性質であり、一般には2-coreの全頂点が単純閉路上にあるとも限らない。具体的な反例は下位単元の複数閉路の注意で確認する。最大の誘導 k-core を求めることと、最大密度などの最適化を混同しない。
下位単元
- 単一サイクル成分とgraph core — 水色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
導入対象の目安: 水色(1200–1599)。辺数と頂点数から閉路数を読み、次数条件で残る核を取り出す入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-graph-core-peeling
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- DFS時刻とlowlink値による橋・関節点の判定。