マトロイド交差定理(matroid intersection theorem)とは、同じ有限集合 $E$ の上の 2 つのマトロイドについて、両方で独立な集合の最大の大きさが、階数関数 $r_1,r_2$ による $\min_{X\subseteq E}(r_1(X)+r_2(E\setminus X))$ に等しいという Edmonds の定理である。共通独立集合を交換グラフの最短の増加路に沿って入れ替えて 1 つずつ大きくし、増加路がなくなった時点で等号を与える $X$ が得られる。二部グラフの Kőnig–Egerváry の定理、マトロイドで独立な横断についての Rado の定理を含み、マトロイドが 3 つになると最大の大きさを求めることは NP 困難になる。
前提知識: マトロイド, 二部グラフ, マッチング(グラフ理論)
マトロイド交差定理(matroid intersection theorem)は、同じ有限集合 $E$ の上の 2 つのマトロイド $M_1,M_2$ について、両方で独立な集合(共通独立集合)の最大の大きさを、階数関数 $r_1,r_2$ で
$$
\max\{\lvert I\rvert\mid I\text{ は }M_1\text{ でも }M_2\text{ でも独立}\}=\min_{X\subseteq E}\bigl(r_1(X)+r_2(E\setminus X)\bigr)
$$
と表す定理である。Edmonds による(Edm70。CLSSW19 p. 4 は「Edmonds の min-max 定理」としてこの等式を述べ、出典にこの論文を挙げる)。
二部グラフのマッチングは、左の頂点ごとに辺を 1 本までとする条件と、右の頂点ごとに 1 本までとする条件の両方をみたす辺集合であり、それぞれの条件はマトロイドを定める。したがって二部グラフの最大マッチングは 2 つのマトロイドの共通独立集合の問題になり、上の等式は最大マッチングと最小頂点被覆が等しいという Kőnig–Egerváryの定理 を含む。全域木の辺をすべて異なる色にとる問題、横断(相異なる代表元)を与えられたマトロイドで独立にとる問題も同じ形をしている。一方、マトロイドが 3 つになると、共通独立集合の最大の大きさを求めることは NP 困難になる。
この記事では、交換グラフの最短路による増加の方法で主定理を証明し(thm-mi-main)、Kőnig–Egerváry の定理と Rado の定理(独立な横断の存在)を導く。3 つのマトロイドの場合が NP 困難であることも示す。
| 内容 | 場所 |
|---|---|
| 共通独立集合と弱い不等式 | def-mi-common、lem-mi-weak |
| 主定理 | thm-mi-main |
| 交換グラフと増加 | def-mi-exchange、prop-mi-augment、prop-mi-stuck |
| 系 | cor-mi-konig、cor-mi-rado |
| 3 つのマトロイド | prop-mi-three |
マトロイドの公理(I1)〜(I3)、階数関数、閉路、閉包は マトロイド の定義・命題のとおりとする。$A\cup\{e\}$ を $A+e$、$A\setminus\{e\}$ を $A-e$ と書く。マトロイド $M=(E,\mathcal I)$ の階数関数 $r$ は、$A\subseteq E$ に、$A$ に含まれる独立集合の最大の大きさを対応させる。
$M_1=(E,\mathcal I_1)$、$M_2=(E,\mathcal I_2)$ を同じ有限集合 $E$ の上のマトロイドとし、階数関数を $r_1,r_2$ とする。$\mathcal I_1\cap\mathcal I_2$ の元を 共通独立集合 といい、その大きさの最大値を $\nu(M_1,M_2)$ と書く。
$\emptyset$ は共通独立集合なので $\nu(M_1,M_2)$ は定まる。
共通独立集合 $I$ と $X\subseteq E$ について $\lvert I\rvert\le r_1(X)+r_2(E\setminus X)$ である。
$I\cap X$ は $M_1$ で独立で $X$ に含まれるので $\lvert I\cap X\rvert\le r_1(X)$、$I\setminus X$ は $M_2$ で独立で $E\setminus X$ に含まれるので $\lvert I\setminus X\rvert\le r_2(E\setminus X)$ である。両者を足せばよい。$\square$
同じ有限集合 $E$ の上のマトロイド $M_1,M_2$ について
$$
\nu(M_1,M_2)=\min_{X\subseteq E}\bigl(r_1(X)+r_2(E\setminus X)\bigr)
$$
である。さらに、空集合から始めて prop-mi-augment の増加を繰り返すと、増加できなくなった時点の共通独立集合 $I$ は大きさ $\nu(M_1,M_2)$ をもち、prop-mi-stuck の $R$ について $X=E\setminus R$ が右辺の最小値を与える。
共通独立集合 $I$ を 1 つずつ大きくする。$I$ から元をいくつか除き、それより 1 つ多い元を加える入れ替えを、交換グラフ(def-mi-exchange)の道として探す。最短の道で入れ替えれば共通独立集合のままで(prop-mi-augment)、道がなければ等号を与える $X$ が見つかる(prop-mi-stuck)。証明は prf-mi-main にまとめる。
$I$ を共通独立集合とする。$E$ を頂点の集合とし、$y\in I$、$x\in E\setminus I$ について次の弧を引いた有向グラフ $D(I)$ を 交換グラフ という。
この弧の向きは CLSSW19 §2.1(p. 8)の交換グラフと同じである。弧は $I$ と $E\setminus I$ の間にしかないので、増加路は $x_0\to y_1\to x_1\to\dots\to y_m\to x_m$($x_i\notin I$、$y_i\in I$)の形をしている。弧 $x_{i-1}\to y_i$ は $M_2$ での、弧 $y_i\to x_i$ は $M_1$ での入れ替えを表す。
マトロイド $M=(E,\mathcal I)$ の閉包 $\operatorname{cl}(A)=\{e\mid r(A+e)=r(A)\}$ について、$B\subseteq\operatorname{cl}(A)$ なら $\operatorname{cl}(B)\subseteq\operatorname{cl}(A)$ である($B\subseteq B'$ なら $\operatorname{cl}(B)\subseteq\operatorname{cl}(B')$ であることは劣モジュラ性から従い、$\operatorname{cl}(\operatorname{cl}(A))=\operatorname{cl}(A)$ は マトロイド の命題「閉包とフラットの性質」の 1)。また $A$ が独立で $e\notin A$ なら、$A+e$ が独立であることと $e\notin\operatorname{cl}(A)$ は同値である。
$M=(E,\mathcal I)$ をマトロイド、$I\in\mathcal I$ とし、相異なる $y_1,\dots,y_m\in I$ と相異なる $x_1,\dots,x_m\in E\setminus I$ が次をみたすとする。
$m$ についての帰納法で示す。$m=0$ なら $I'=I$ である。$m\ge1$ とし、組 $(y_i,x_i)$($2\le i\le m$)は同じ仮定をみたすので、帰納法の仮定から $J:=(I\setminus\{y_2,\dots,y_m\})\cup\{x_2,\dots,x_m\}$ は独立である。$I'=J-y_1+x_1$ を示せばよい。
$A:=I-y_1$ とおく。$A$ は独立で、1 から $A+x_1$ は独立なので $x_1\notin\operatorname{cl}(A)$ である。$j\ge2$ では 2 から $A+x_j$ は従属なので $x_j\in\operatorname{cl}(A)$ である。よって $J-y_1=(A\setminus\{y_2,\dots,y_m\})\cup\{x_2,\dots,x_m\}\subseteq\operatorname{cl}(A)$ であり、$\operatorname{cl}(J-y_1)\subseteq\operatorname{cl}(A)$ となるので $x_1\notin\operatorname{cl}(J-y_1)$ である。$J-y_1$ は独立集合 $J$ の部分集合で独立であり、$x_1\notin J-y_1$ なので、$J-y_1+x_1=I'$ は独立である。$\square$
$I\in\mathcal I$ とし、$Z\subseteq E\setminus I$ のどの元 $z$ についても $I+z\notin\mathcal I$ とする。このとき $r(I\cup Z)=\lvert I\rvert$ である。
$r(I\cup Z)>\lvert I\rvert$ なら、$I\cup Z$ に含まれる大きさ $\lvert I\rvert+1$ の独立集合 $K$ がある。(I3)により $z\in K\setminus I\subseteq Z$ で $I+z$ が独立なものがあり、仮定に反する。$\square$
$I$ を共通独立集合とし、$P=(x_0,y_1,x_1,\dots,y_m,x_m)$ を $D(I)$ の増加路のうち頂点の数が最小のものとする。このとき $I\triangle P:=(I\setminus\{y_1,\dots,y_m\})\cup\{x_0,\dots,x_m\}$ は大きさ $\lvert I\rvert+1$ の共通独立集合である。
$P$ は道なので頂点は相異なり、$\lvert I\triangle P\rvert=\lvert I\rvert+1$ である。最短性から、次の「近道」がない。
$M_1$ で独立であること.組 $(y_i,x_i)$($1\le i\le m$)は、弧 $y_i\to x_i$ により $I-y_i+x_i\in\mathcal I_1$ をみたし、(c) により $i< j$ なら $I-y_i+x_j\notin\mathcal I_1$ をみたす。lem-mi-triangular により $K:=(I\setminus\{y_1,\dots,y_m\})\cup\{x_1,\dots,x_m\}$ は $M_1$ で独立である。$K+x_0=I\triangle P$ が $M_1$ で独立であることを示す。$Z:=\{x_1,\dots,x_m\}$ とおくと、(a) により lem-mi-rank が使え、$r_1(I\cup Z)=\lvert I\rvert$ である。$K+x_0$ が従属なら、$\lvert I+x_0\rvert=\lvert I\rvert+1>\lvert K\rvert$ と(I3)から、$z\in(I+x_0)\setminus K$ で $K+z\in\mathcal I_1$ となるものがある。$K+x_0$ は従属と仮定したので $z\ne x_0$ であり、$z\in I\setminus K=\{y_1,\dots,y_m\}$ である。すると $K+z\subseteq I\cup Z$ は大きさ $\lvert I\rvert+1$ の独立集合となり、$r_1(I\cup Z)=\lvert I\rvert$ に反する。
$M_2$ で独立であること.組 $(y_i,x_{i-1})$ を $i=m,m-1,\dots,1$ の順に並べる。弧 $x_{i-1}\to y_i$ により $I-y_i+x_{i-1}\in\mathcal I_2$ であり、(d) により $i>j$ なら $I-y_i+x_{j-1}\notin\mathcal I_2$ である。この並べ方で lem-mi-triangular の仮定 2 が成り立つので、$K':=(I\setminus\{y_1,\dots,y_m\})\cup\{x_0,\dots,x_{m-1}\}$ は $M_2$ で独立である。$I+x_m$ は $M_2$ で独立で、(b) により $x_0,\dots,x_{m-1}$ は $X_2$ に入らない。$M_1$ の場合と同じ議論($x_0$ を $x_m$ に、$Z$ を $\{x_0,\dots,x_{m-1}\}$ に置き換える)で、$K'+x_m=I\triangle P$ は $M_2$ で独立である。$\square$
最短でない増加路で入れ替えると、共通独立集合にならないことがある(ex-mi-counter の 4 行目)。この命題は CLSSW19 Lemma 6(p. 8)として、証明なしに既知の事実として述べられている。
共通独立集合 $I$ について $D(I)$ に増加路がないとする。$X_1$ の頂点から有向道で到達できる頂点の集合を $R$ とおく($X_1\subseteq R$)。このとき
$$
r_1(E\setminus R)=\lvert I\setminus R\rvert,\qquad r_2(R)=\lvert I\cap R\rvert
$$
であり、$\lvert I\rvert=r_1(E\setminus R)+r_2(R)$ となる。
増加路がないので $R\cap X_2=\emptyset$ である。
$r_2(R)=\lvert I\cap R\rvert$.$I\cap R$ は $M_2$ で独立なので $r_2(R)\ge\lvert I\cap R\rvert$ である。$r_2(R)>\lvert I\cap R\rvert$ とすると、$R$ に含まれる大きさ $r_2(R)$ の独立集合と(I3)から、$x\in R\setminus I$ で $(I\cap R)+x\in\mathcal I_2$ となるものがある。$x\in R$ なので $x\notin X_2$、つまり $I+x$ は $M_2$ で従属であり、マトロイド の補題「基本閉路」により $I+x$ はただ 1 つの閉路 $C\ni x$ を含む。$(I\cap R)+x$ は独立なので $C\not\subseteq(I\cap R)+x$ であり、$y\in C\cap(I\setminus R)$ がある。$I+x-y$ は唯一の閉路 $C$ を含まないので独立であり、$D(I)$ に弧 $x\to y$ がある。$x\in R$ から $y\in R$ となり、$y\notin R$ に反する。
$r_1(E\setminus R)=\lvert I\setminus R\rvert$.同様に、$r_1(E\setminus R)>\lvert I\setminus R\rvert$ なら $x\in(E\setminus R)\setminus I$ で $(I\setminus R)+x\in\mathcal I_1$ となるものがある。$x\notin R\supseteq X_1$ なので $I+x$ は $M_1$ で従属であり、ただ 1 つの閉路 $C\ni x$ は $y\in C\cap I\cap R$ を含む。$I-y+x\in\mathcal I_1$ なので弧 $y\to x$ があり、$y\in R$ から $x\in R$ となって矛盾する。
最後の等式は $\lvert I\rvert=\lvert I\setminus R\rvert+\lvert I\cap R\rvert$ による。$\square$
lem-mi-weak により、どの共通独立集合 $I$ とどの $X$ についても $\lvert I\rvert\le r_1(X)+r_2(E\setminus X)$ なので、左辺は右辺以下である。
$I_0:=\emptyset$ から始め、$D(I_k)$ に増加路があれば最短のものをとり、prop-mi-augment により $I_{k+1}:=I_k\triangle P$ とする。$\lvert I_k\rvert=k$ で共通独立集合は $\lvert E\rvert$ 個以下の元しかもたないので、この手続きは有限回で止まる。止まったときの $I$ には増加路がなく、prop-mi-stuck の $R$ について $X:=E\setminus R$ とおけば $\lvert I\rvert=r_1(X)+r_2(E\setminus X)$ である。よって
$$
\min_{X}\bigl(r_1(X)+r_2(E\setminus X)\bigr)\le\lvert I\rvert\le\nu(M_1,M_2)
$$
であり、弱い不等式と合わせて等号が成り立つ。$\square$
各段は交換グラフを作り幅優先探索で最短の増加路を探すだけなので、独立かどうかを答える手続き(独立性の神託)を $O(\lvert I\rvert\,\lvert E\rvert)$ 回呼べば済み、段の数は $\nu(M_1,M_2)+1$ 以下である。$n=\lvert E\rvert$、$r=\nu(M_1,M_2)$ として、CLSSW19 は、神託 1 回の時間を $T$ として $O(nrT\log r)$ 時間の算法を与えている(同論文の要旨、p. 1)。
$E$ の分割 $E=E_1\sqcup\dots\sqcup E_k$ について、各 $E_j$ から高々 1 元しか含まない集合を独立とすると、マトロイドになる。(I1)(I2)は明らかで、$\lvert I\rvert<\lvert J\rvert$ なら $J$ が触れる塊のうち $I$ が触れないものがあり、その塊の $J$ の元を $I$ に加えられるからである。これを 分割マトロイド といい、階数は $r(X)=\#\{j\mid X\cap E_j\ne\emptyset\}$ である。
有限の二部グラフ $G$(頂点の 2 分割 $U\sqcup W$、辺集合 $E$)で、マッチングの大きさの最大値は、すべての辺に触れる頂点集合(頂点被覆)の大きさの最小値に等しい。
各頂点 $u\in U$ に接続する辺の集合で $E$ を分割した分割マトロイドを $M_1$、$W$ の側で同じく作ったものを $M_2$ とする。辺集合が共通独立であることは、どの頂点にも高々 1 本しか接続しないこと、つまりマッチングであることと同じである。$X\subseteq E$ について、$r_1(X)$ は $X$ の辺の $U$ 側の端点の数、$r_2(E\setminus X)$ は $E\setminus X$ の辺の $W$ 側の端点の数で、それらの端点を合わせた集合 $C_X$ は頂点被覆で $\lvert C_X\rvert=r_1(X)+r_2(E\setminus X)$ である。逆に頂点被覆 $C$ について、$U$ 側の端点が $C$ に入る辺の集合を $X$ とおくと、$E\setminus X$ の辺は $W$ 側の端点が $C$ に入るので $r_1(X)+r_2(E\setminus X)\le\lvert C\cap U\rvert+\lvert C\cap W\rvert=\lvert C\rvert$ である。よって thm-mi-main の右辺は頂点被覆の大きさの最小値に等しい。$\square$
別の証明と行列の形は Kőnig–Egerváryの定理 にある。グラフが二部でないと等号が成り立たないことがある(ex-mi-counter の 3 行目)。
$M$ を有限集合 $S$ の上のマトロイド(階数関数 $r_M$)、$A_1,\dots,A_m\subseteq S$ とする。相異なる $s_1\in A_1,\dots,s_m\in A_m$ で $\{s_1,\dots,s_m\}$ が $M$ で独立なものがあるための必要十分条件は、すべての $J\subseteq\{1,\dots,m\}$ について
$$
r_M\Bigl(\bigcup_{j\in J}A_j\Bigr)\ge\lvert J\rvert
$$
が成り立つことである。
必要性:$\{s_j\mid j\in J\}$ は $\bigcup_{j\in J}A_j$ に含まれる大きさ $\lvert J\rvert$ の独立集合である。
十分性:$E:=\{(j,s)\mid s\in A_j\}$ とし、$\pi(j,s):=s$ とおく。$M_1$ を第 1 成分による分割マトロイド、$M_2$ を「$\pi$ が $F$ の上で単射で $\pi(F)$ が $M$ で独立」なときに $F\subseteq E$ を独立とする族とする。$M_2$ はマトロイドである:(I1)(I2)は明らかで、$\lvert F\rvert<\lvert F'\rvert$ なら $\lvert\pi(F)\rvert<\lvert\pi(F')\rvert$ なので、$M$ の(I3)により $s\in\pi(F')\setminus\pi(F)$ で $\pi(F)+s$ が独立なものがあり、$F'$ の $s$ の上の元を $F$ に加えればよい。階数は $r_2(Z)=r_M(\pi(Z))$ である。求める横断は、大きさ $m$ の共通独立集合にほかならない。
$X\subseteq E$ をとり、$X$ の元を 1 つも含まない添字 $j$ の集合を $J$ とする。$r_1(X)=m-\lvert J\rvert$ であり、$j\in J$ なら $\{j\}\times A_j\subseteq E\setminus X$ なので $r_2(E\setminus X)\ge r_M(\bigcup_{j\in J}A_j)\ge\lvert J\rvert$ である。よって $r_1(X)+r_2(E\setminus X)\ge m$ で、thm-mi-main により $\nu(M_1,M_2)\ge m$ となる。$\square$
$M$ を自由マトロイド(すべての部分集合が独立)にとると、$r_M(A)=\lvert A\rvert$ なので Hallの結婚定理 になる。
連結なグラフ $G=(V,E)$ の辺に色が塗られているとする。$M_1$ を $G$ のグラフ的マトロイド(マトロイド の命題「グラフ的マトロイド」)、$M_2$ を色による分割マトロイドとすると、共通独立集合はどの 2 辺も色が異なる森である。thm-mi-main から、そのような森の辺の数の最大値は、使われている色の集合の部分集合 $K$ にわたる
$$
\min_K\bigl(\lvert V\rvert-c(E_K)+(\text{使われている色の数}-\lvert K\rvert)\bigr)
$$
に等しい。ここで $E_K$ は色が $K$ に入る辺の集合、$c(E_K)$ は $(V,E_K)$ の連結成分の数である。とくに、すべての色が異なる全域木があることと、どの $K$ についても $c(E_K)-1$ が $K$ に入らない色の数以下であることは同値である。
$X\subseteq E$ について、$E\setminus X$ に現れない色の集合を $K$ とすると $E_K\subseteq X$ なので $r_1(E_K)\le r_1(X)$ であり、$E\setminus E_K$ に現れる色は $E\setminus X$ に現れる色と同じなので $r_2(E\setminus E_K)=r_2(E\setminus X)$ である。よって右辺の最小は $X=E_K$ の形でとれ、$r_1(E_K)=\lvert V\rvert-c(E_K)$ である。
4 頂点の閉路 $1\,2\,3\,4$ の辺 $12,23,34,41$ を赤・赤・青・緑と塗る。$K=\{\text{青},\text{緑}\}$ では $c(E_K)-1=1$ で、$K$ に入らない色は赤の 1 つである。ほかの $K$ でも条件が成り立ち、辺 $12,34,41$ がすべての色が異なる全域木である。
同じ $E$ の上の 3 つのマトロイドの共通独立集合の最大の大きさについては、thm-mi-main のような等式は成り立たない(ex-mi-counter の 1 行目)。計算も難しい。
有向グラフ $D$(頂点 $n$ 個)の弧の集合 $E$ の上に、次の 3 つのマトロイドを作る。$M_{\mathrm{out}}$:弧を始点で分けた分割マトロイド。$M_{\mathrm{in}}$:弧を終点で分けた分割マトロイド。$M_{\mathrm g}$:向きを忘れた多重グラフのグラフ的マトロイド。このとき、3 つの共通独立集合で大きさ $n-1$ のものがあることと、$D$ がすべての頂点をちょうど 1 回ずつ通る有向道(有向 Hamilton 道)をもつことは同値である。したがって、P $\ne$ NP なら、3 つのマトロイドの共通独立集合の最大の大きさを多項式時間で求める方法はない。
有向 Hamilton 道の弧の集合は、各頂点から出る弧も入る弧も高々 1 本で、閉路を含まないので、大きさ $n-1$ の共通独立集合である。逆に $F$ が大きさ $n-1$ の共通独立集合なら、$F$ は $n$ 頂点の森で辺が $n-1$ 本なので全域木である(マトロイド の命題「グラフ的マトロイド」の $c(F)=n-(n-1)=1$)。各頂点の次数は入る弧と出る弧の 1 本ずつ以下なので 2 以下であり、次数が 2 以下の木は道である。道の内部の頂点は 2 本の弧に接し、入る弧と出る弧が 1 本ずつなので、弧の向きはそろい、$F$ は有向 Hamilton 道である。
後半は、有向 Hamilton 閉路の判定が NP 完全であること(NP完全 の節「ほかの NP完全問題」)から、頂点を 1 つ分ける帰着で従う。
$D$ の頂点 $v$ を、$v$ から出る弧だけをもつ $v^+$ と $v$ に入る弧だけをもつ $v^-$ に分けた有向グラフ $D'$ が有向 Hamilton 道をもつことは、$D$ が有向 Hamilton 閉路をもつことと同値である($D'$ の道は入る弧のない $v^+$ から始まり出る弧のない $v^-$ で終わるしかない。$n\ge2$)。3 つのマトロイドは $D'$ から多項式時間で作れ、独立性も多項式時間で判定できるので、最大の大きさが多項式時間で求まれば有向 Hamilton 閉路の判定が多項式時間でできることになる。$\square$
独立系 $\mathcal I_1\cap\dots\cap\mathcal I_p$ の上の貪欲法がどれだけ最適に近いかは Rado–Edmondsの定理 の命題「マトロイドの共通部分」にある。
道 $a\,b\,c\,d$(辺 $e_1=ab$、$e_2=bc$、$e_3=cd$)を二部グラフ($U=\{a,c\}$、$W=\{b,d\}$)とみて、prf-mi-konig の $M_1$($U$ 側)、$M_2$($W$ 側)をとる。$I=\{e_2\}$ では $X_1=\{e_1\}$、$X_2=\{e_3\}$ で、最短の増加路 $e_1\to e_2\to e_3$ で入れ替えると大きさ 2 のマッチング $\{e_1,e_3\}$ が得られる。これは二部グラフの交互道による増加と同じ操作である。
$I+e_1$ は $M_1$ で独立($a\ne c$)だが $M_2$ では $e_1,e_2$ が $b$ を共有して従属、$I+e_3$ は $M_1$ で $c$ を共有して従属、$M_2$ で独立である。$I-e_2+e_3=\{e_3\}$ は $M_1$ で独立なので弧 $e_2\to e_3$、$I-e_2+e_1=\{e_1\}$ は $M_2$ で独立なので弧 $e_1\to e_2$ がある。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| マトロイドが 2 つ(thm-mi-main) | $E=\{x,y,z\}$ と分割マトロイド $\{x,y\}\vert\{z\}$、$\{y,z\}\vert\{x\}$、$\{x,z\}\vert\{y\}$ | 共通独立集合の最大の大きさ $1$ が、3 分割 $X_1\sqcup X_2\sqcup X_3$ にわたる $\sum_ir_i(X_i)$ の最小値 $2$ と等しくない |
| 両方がマトロイド(thm-mi-main) | $E=\{1,2,3\}$、$M_1$ は分割マトロイド $\{1,2\}\vert\{3\}$、$\mathcal I_2=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\}\}$(増加公理が満たされない独立系) | $\nu=1$ だが $\min_X(r_1(X)+r_2(E\setminus X))=2$ |
| グラフが二部(cor-mi-konig) | 三角形 $K_3$ | 最大マッチングの大きさ $1$ と最小頂点被覆の大きさ $2$ が等しくない |
| 増加路が最短(prop-mi-augment) | $E=\{a,b,c\}$、$M_1$ は $\{a,b\}$ だけが閉路、$M_2$ は $\{b,c\}$ だけが閉路、$I=\{a\}$、増加路 $c\to a\to b$ | $I\triangle P=\{b,c\}$ は $M_2$ で従属で、共通独立集合にならない |
どの行も、表の右の欄の主張を直接確かめられる。
1 行目:どの 2 元もどれかのマトロイドで同じ塊に入るので、共通独立集合は 1 元以下である。一方、$X_i$ が空でなければ $r_i(X_i)\ge1$ で、空でない $X_i$ が 1 つだけなら $X_i=E$ で $r_i(E)=2$ なので、どの 3 分割でも和は $2$ 以上であり、$X_1=\{x,y\}$、$X_2=\{z\}$、$X_3=\emptyset$ で $2$ になる。
2 行目:$\mathcal I_2$ は部分集合で閉じているが、$\{3\}$ と $\{1,2\}$ がともに極大で大きさが違うので増加公理をみたさない。$\mathcal I_2$ の大きさ 2 の元 $\{1,2\}$ は $M_1$ で従属なので $\nu=1$ である。$r_2(A)$ を $A$ に含まれる $\mathcal I_2$ の元の最大の大きさとすると、$r_1(X)\ge1$($X\ne\emptyset$)、$r_2(E\setminus X)\ge1$($X\ne E$)、$r_1(E)=r_2(E)=2$ なので、どの $X$ でも和は $2$ 以上である。
3 行目:$K_3$ のどの 2 辺も頂点を共有し、1 頂点ではその頂点を通らない辺が残る。
4 行目:$I+c$ は両方で独立なので $c\in X_1\cap X_2$ で、最短の増加路は $c$ だけである。$I-a+c=\{c\}$ は $M_2$ で独立なので弧 $c\to a$、$I-a+b=\{b\}$ は $M_1$ で独立なので弧 $a\to b$ があり、$I+b=\{a,b\}$ は $M_2$ で独立なので $b\in X_2$ である。この長い増加路では prf-mi-augment の近道 (b) があり、$\{b,c\}$ は $M_2$ の閉路になる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する