Matroidの独立性・greedy・線形交差

概要

安いものから選び、条件を壊す候補だけを飛ばす貪欲法は、どの選択問題でも正しいわけではない。ベクトルの線形独立性や、辺集合が森であるという条件では、選択の正しさを「独立集合」と「交換公理」で共通に説明できる。この構造を matroid(マトロイド)と呼ぶ。

まず一つの matroid で何を確かめれば貪欲法を使えるかを学び、その後に二つの独立性条件を同時に課す場合へ進む。

考え方

三ベクトルから独立集合・基底・rankを知る

F2\mathbf F_2 は、成分を 0,10,1 とし、加算を XOR で行う二元体である。選べる要素を、次の三つのベクトルとする。価格は順に 1,2,31,2,3 とする。

a=(1,0),b=(0,1),c=(1,1)a=(1,0),\qquad b=(0,1),\qquad c=(1,1)

選べる要素全体の集合を E={a,b,c}E=\{a,b,c\} と書く。ここでは、選んだベクトルが線形独立である集合、つまり空でない部分集合の XOR が 00 にならない集合を独立集合とする。全ての部分集合を調べると、次のようになる。

選ぶ集合独立性と理由
∅\varnothing独立。非空の部分集合がない
{a},{b},{c}\{a\},\{b\},\{c\}独立。どれも零ベクトルではない
{a,b},{a,c},{b,c}\{a,b\},\{a,c\},\{b,c\}独立。異なる二本なので、一本でも二本の XOR でも 00 にならない
{a,b,c}\{a,b,c\}従属。a⊕b⊕c=0a\oplus b\oplus c=0 になる

独立集合に、残りのどの要素も追加できなくなったら極大という。「極大」は追加できないという意味で、個数が最大かどうかは定義に含まない。極大な独立集合を基底と呼ぶ。この例の基底は三つの二要素集合で、価格の合計はそれぞれ 3,4,53,4,5 である。

集合 X⊆EX\subseteq E に含まれる独立集合の最大サイズを rank⁡(X)\operatorname{rank}(X)(rank、階数)と呼ぶ。この例では rank⁡(E)=2\operatorname{rank}(E)=2 であり、どの基底も二本で全ベクトルを XOR で作れる。価格順に a,ba,b を採用すると、c=a⊕bc=a\oplus b は作れる値を増やさないので拒否し、費用 33 の最小基底を得る。各判定の手順と最適性は子単元の matroid greedyで追う。

貪欲法を支える三つの公理

一般に、有限の要素集合 EE と、独立とみなす部分集合を全て集めた族 I\mathcal I を考える。次の三条件を満たす組 (E,I)(E,\mathcal I) が matroid である。

  1. 空集合は独立である: ∅∈I\varnothing\in\mathcal I。
  2. 独立集合の部分集合も独立である(遺伝性)。
  3. 独立集合 A,B∈IA,B\in\mathcal I が ∣A∣<∣B∣|A|<|B| を満たすなら、ある e∈B∖Ae\in B\setminus A を AA に加えても独立である(交換公理)。

三つ目は、まだ選択数が少ない側には、大きい独立集合から一つ追加する余地があるという条件である。例えば A={c},B={a,b}A=\{c\},B=\{a,b\} なら、a,ba,b のどちらを AA に追加しても独立になる。

交換公理により、極大独立集合は全て同じサイズになる。もし基底 AA より大きい独立集合 BB があれば、AA に一つ追加できて極大性に反するからである。同じ議論は任意の候補集合 X⊆EX\subseteq E の中でも成り立つため、XX 内で極大まで選べばサイズは必ず rank⁡(X)\operatorname{rank}(X) になる。これが、重み順に見た候補のどの範囲でも、貪欲法が選択数で損をしない理由になる。

線形独立性と森では、何を判定するか

**独立性 oracle(判定手続き)**は、与えた集合が独立かを返す処理を指す。貪欲法では、現在の独立集合に候補を一つ加えてよいかを問い合わせる。matroid であることの証明と、判定を速く実装することは別の仕事である。

  • 線形 matroid: ベクトルの線形独立な集合を使う。空集合・遺伝性は線形独立性から従う。交換公理は、∣A∣<∣B∣|A|<|B| のとき、独立な BB の全ベクトルが AA の張る空間に入ることはない、と次元を比較すれば分かる。oracle は候補を現在の基底で消去し、零になれば拒否、零でなければ採用して基底を更新する。F2\mathbf F_2 上の実装は XOR線形基底へ進む。
  • グラフ的 matroid: 無向グラフの辺を要素とし、閉路を持たない辺集合(森)を独立とする。辺を減らしても森である。森 A,BA,B で ∣A∣<∣B∣|A|<|B| のとき、BB の全辺が AA の各連結成分内に収まると仮定すると、各成分内で BB が持てる辺数は頂点数から一を引いた数以下なので、合計も ∣A∣|A| 以下となり矛盾する。従って AA の異なる成分を結ぶ BB の辺を追加できる。oracle は Union-Find で両端が別成分なら採用・併合し、同じ成分なら拒否する。重みの小さい順に行うと Kruskal 法になる。

二つのmatroidを同時に課すと交換できないことがある

四頂点を順に結ぶ三辺の道を考える。辺を e1={v0,v1}e_1=\{v_0,v_1\}、e2={v1,v2}e_2=\{v_1,v_2\}、e3={v2,v3}e_3=\{v_2,v_3\} とする。端点を共有しない辺の集合を matching(マッチング)という。この道の matching は、空集合、三つの一辺集合、{e1,e3}\{e_1,e_3\} の計五つである。

A={e2}A=\{e_2\} と B={e1,e3}B=\{e_1,e_3\} はどちらも matching で、∣A∣<∣B∣|A|<|B| である。しかし e1e_1 を AA に足すと v1v_1、e3e_3 を足すと v2v_2 が重なる。B∖AB\setminus A のどれも追加できず、交換公理が壊れる。AA は極大だが最大ではなく、中辺を先に採用するだけで最大の二辺を逃す。

この matching の条件は、実は二つの matroid の共通条件である。道を二部グラフとして、片側を U={v0,v2}U=\{v_0,v_2\}、もう片側を V={v1,v3}V=\{v_1,v_3\} に分ける。

課す条件辺の分割(各グループから高々一本)
UU 側の各頂点で高々一本{e1},{e2,e3}\{e_1\},\{e_2,e_3\}
VV 側の各頂点で高々一本{e1,e2},{e3}\{e_1,e_2\},\{e_3\}

それぞれは**分割 matroid(partition matroid)**である。空集合と遺伝性を満たし、∣A∣<∣B∣|A|<|B| なら、BB が一本選んでいて AA がまだ選んでいないグループがあるので、そこから一辺追加できる。一方、両方を同時に満たすと matching になり、上の反例が生じる。一方で追加できる辺が、もう一方でも追加できるとは限らないのである。

成立条件と計算量

単一 matroid の最適基底は、重み順に oracle で独立性を確かめる貪欲法で求まる。候補数を m=∣E∣m=|E|、一回の追加判定・更新の費用を高々 TT とすると、ソートを含む時間は O(mlog⁡m+mT)O(m\log m+mT) である。具体的な判定費用と保存領域は oracle の実装で決まる。

二つの matroid の共通独立集合を最適化するmatroid 交差では、この貪欲法の保証は失われる。一般の matching や交差を同じ選択手順で解けるとは考えない。線形matroid交差の乱択rank判定では、二つの制約がともに線形表現できる場合に、共通独立集合の最大サイズを乱択行列の rank で調べる。ABC399 G の森林・色別上限もこの側の問題であり、集合の復元まで rank 一回でできるとは限らない。

下位単元

問題一覧

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

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

前提・学習成果・出典

導入対象の目安: 黄色(2000–2399)。独立性と交換公理を使い、貪欲法の成立範囲を整理する入口。

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

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-matroid-theory

前提と範囲

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

直接の前提単元: なし。

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

このUnitでは扱わないもの

  • 線形方程式一般、graph matching一般、および交換公理を用いない単なる貪欲選択。

根拠