マトロイド和定理

同義語:matroid union theoremマトロイドの和matroid unionマトロイド合併定理

概要

マトロイド和定理(matroid union theorem)とは、同じ有限集合 $E$ の上のマトロイド $M_1,\dots,M_k$ の独立集合を 1 つずつとって合併した集合の全体がマトロイドになり、その階数関数が $\rho(X)=\min_{Y\subseteq X}(\lvert X\setminus Y\rvert+\sum_ir_i(Y))$ で与えられるという定理である。$E$ を $k$ 枚写した直和と、同じ元の写しを 1 つまでとする分割マトロイドの共通独立集合の問題に置き換え、マトロイド交差定理から階数の式が得られる。同じマトロイドの写しの和に当てると、台集合を $k$ 個の独立集合に分ける条件と、互いに素な基を $k$ 個もつ条件(Edmonds の被覆と詰め込みの定理)が従い、グラフでは森による被覆と辺素な全域木の条件になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: マトロイド, マトロイド交差定理

マトロイド和定理(matroid union theorem)は、同じ有限集合 $E$ の上のマトロイド $M_1,\dots,M_k$ について、各 $M_i$ の独立集合を 1 つずつとって合併した集合の全体がまたマトロイドになり、その階数関数が
$$ \rho(X)=\min_{Y\subseteq X}\Bigl(\lvert X\setminus Y\rvert+\sum_{i=1}^k r_i(Y)\Bigr) $$
で与えられる、という定理である($r_i$ は $M_i$ の階数関数)。この階数の式は Nash-Williams に帰される(LR82 Theorem 6、p. 174)。$k=2$ の場合の式は Oxl03 Exercise 3.12(p. 13)にも述べられている。
$M_1=\dots=M_k=M$ とおくと、合併がどこまで大きくなるかから、$E$ を $k$ 個の独立集合に分けられる条件と、$M$ が互いに素な基を $k$ 個もつ条件が読み取れる。前者は Edmonds の被覆の定理(Edm65a Theorem 1、p. 69)、後者は Edmonds の詰め込みの定理(Edm65b Theorem 2、p. 74)であり、グラフ的マトロイドに当てると、辺を $k$ 個の森で覆う条件と、$k$ 本の辺素な全域木をもつ条件になる(Tutte–Nash-Williamsの定理)。
この記事では、直和と射影を使って和の問題を マトロイド交差定理 に帰着し、主定理を証明する(thm-mu-main)。そのあと被覆と詰め込みの定理を導く。

内容場所
和の定義と例def-mu-union、ex-mu-uniform
主定理thm-mu-main
直和と持ち上げlem-mu-sum、lem-mu-lift
交差定理による最大値prop-mu-max、lem-mu-axioms
系cor-mu-cover、cor-mu-pack
例と反例ex-mu-k5、ex-mu-counter

定義

マトロイドの公理(I1)〜(I3)、階数関数とその性質(R1)〜(R3)、公理系の同値は マトロイド のとおりとする。$A\cup\{e\}$ を $A+e$ と書き、$[k]=\{1,\dots,k\}$ とする。

マトロイドの和

$M_i=(E,\mathcal I_i)$($i\in[k]$)を同じ有限集合 $E$ の上のマトロイドとする。
$$ \mathcal I_1\vee\dots\vee\mathcal I_k:=\{I_1\cup\dots\cup I_k\mid I_i\in\mathcal I_i\ (i\in[k])\} $$
とおき、組 $(E,\mathcal I_1\vee\dots\vee\mathcal I_k)$ を $M_1\vee\dots\vee M_k$ と書いて $M_1,\dots,M_k$ の 和(合併)という。$X\subseteq E$ について、$X$ に含まれる $\mathcal I_1\vee\dots\vee\mathcal I_k$ の元の大きさの最大値を $\rho(X)$ と書く。

$\emptyset$ はどの $\mathcal I_i$ にも属するので、$\rho(X)$ は定まる。$I=I_1\cup\dots\cup I_k$ のとき、$I_i':=I_i\setminus(I_1\cup\dots\cup I_{i-1})$ は(I2)により $\mathcal I_i$ に属し、$I$ は互いに素な $I_1',\dots,I_k'$ の合併になる。以下ではこの書き直しを断らずに使う。

一様マトロイドの和

$E=[n]$ とし、$0\le a,b\le n$ とする。一様マトロイド $U_{a,n}$($a$ 元以下の部分集合が独立。マトロイド の例「一様マトロイド」)について $U_{a,n}\vee U_{b,n}=U_{c,n}$、$c=\min(a+b,n)$ である。$c$ 元以下の集合は $a$ 元以下と $b$ 元以下の 2 つに分けられ、逆に 2 つの合併は $a+b$ 元以下だからである。階数の式では、$\lvert X\rvert\le a+b$ なら $Y=\emptyset$ が、$\lvert X\rvert\ge a+b$ なら $Y=X$ が最小値 $\min(\lvert X\rvert,a+b)$ を与える。

和は「各 $M_i$ に 1 つずつ割り当てて合併する」操作なので、元が 2 つ以上の $M_i$ で使えても 1 回しか数えない。最大値 $\rho(X)$ を求めることは、$X$ の元をできるだけ多く $M_1,\dots,M_k$ に配る問題である。

主定理

マトロイド和定理

$M_1,\dots,M_k$ を同じ有限集合 $E$ の上のマトロイドとし、$r_i$ を $M_i$ の階数関数とする。

  1. $M_1\vee\dots\vee M_k$ はマトロイドである。
  2. その階数関数 $\rho$ は、$X\subseteq E$ について
    $$ \rho(X)=\min_{Y\subseteq X}\Bigl(\lvert X\setminus Y\rvert+\sum_{i=1}^k r_i(Y)\Bigr) $$
    で与えられる。

右辺が $\rho(X)$ 以上であることはすぐ分かる。$I=I_1\sqcup\dots\sqcup I_k\subseteq X$ を和の元とすると、どの $Y\subseteq X$ についても
$$ \lvert I\rvert\le\lvert X\setminus Y\rvert+\lvert I\cap Y\rvert\le\lvert X\setminus Y\rvert+\sum_{i=1}^k\lvert I_i\cap Y\rvert\le\lvert X\setminus Y\rvert+\sum_{i=1}^k r_i(Y) $$
だからである($I_i\cap Y$ は $Y$ に含まれる $M_i$ の独立集合)。等号を示すのが主定理の中身である。

証明の組み立て

$E$ を $k$ 枚写した集合 $E\times[k]$ の上に、$i$ 枚目では $M_i$ の独立性を課す直和 $\widehat M$ を作る(lem-mu-sum)。和の元は、$\widehat M$ の独立集合で、同じ元の写しを 2 つ以上含まないものの影にほかならない(lem-mu-lift)。「同じ元の写しは 1 つまで」は分割マトロイドの独立性なので、$\rho(X)$ は 2 つのマトロイドの共通独立集合の最大の大きさになり、マトロイド交差定理 から階数の式が出る(prop-mu-max)。最後に、式の右辺が階数関数の公理をみたすことを確かめ(lem-mu-axioms)、マトロイド の定理「マトロイドの公理系の同値」で 1 を得る(prf-mu-main)。

直和と持ち上げ

$\widehat E:=E\times[k]$ とし、$\pi\colon\widehat E\to E$ を $\pi(e,i)=e$ で定める。$Z\subseteq\widehat E$ と $i\in[k]$ について $Z_i:=\{e\in E\mid(e,i)\in Z\}$ とおく。

直和

$\widehat{\mathcal I}:=\{J\subseteq\widehat E\mid\text{すべての }i\text{ で }J_i\in\mathcal I_i\}$ とおくと、$\widehat M:=(\widehat E,\widehat{\mathcal I})$ はマトロイドであり、その階数関数は $\widehat r(Z)=\sum_{i=1}^k r_i(Z_i)$ である。

(I1)(I2)は各 $\mathcal I_i$ の(I1)(I2)から従う。(I3):$J,J'\in\widehat{\mathcal I}$、$\lvert J\rvert< \lvert J'\rvert$ とする。$\lvert J\rvert=\sum_i\lvert J_i\rvert$ なので、ある $i$ で $\lvert J_i\rvert< \lvert J'_i\rvert$ である。$M_i$ の(I3)により $e\in J'_i\setminus J_i$ で $J_i+e\in\mathcal I_i$ となるものがあり、$J+(e,i)\in\widehat{\mathcal I}$、$(e,i)\in J'\setminus J$ である。
階数:$Z$ に含まれる $\widehat{\mathcal I}$ の元 $J$ は、各 $i$ で $J_i\subseteq Z_i$、$J_i\in\mathcal I_i$ をみたす集合であり、$J_i$ は互いに独立に選べる。よって $\lvert J\rvert=\sum_i\lvert J_i\rvert$ の最大値は $\sum_ir_i(Z_i)$ である。$\square$

持ち上げ

$I\subseteq E$ について、$I\in\mathcal I_1\vee\dots\vee\mathcal I_k$ であることと、$J\in\widehat{\mathcal I}$ で $\pi$ が $J$ の上で単射かつ $\pi(J)=I$ となるものがあることは同値である。

$I=I_1\sqcup\dots\sqcup I_k$(互いに素、$I_i\in\mathcal I_i$)なら、$J:=\bigcup_iI_i\times\{i\}$ は $J_i=I_i$ なので $\widehat{\mathcal I}$ に属し、$I_i$ が互いに素なので $\pi$ は $J$ の上で単射で、$\pi(J)=I$ である。逆に $J$ がそのような集合なら、$I=\pi(J)=J_1\cup\dots\cup J_k$、$J_i\in\mathcal I_i$ である。$\square$

交差定理による最大値

和の最大の大きさ

$X\subseteq E$ について
$$ \rho(X)=\min_{Y\subseteq X}\Bigl(\lvert X\setminus Y\rvert+\sum_{i=1}^k r_i(Y)\Bigr) $$
である。

$\widehat X:=X\times[k]$ とおく。$\widehat X$ の上に 2 つのマトロイドを考える。$N_1$ は $\widehat M$ を $\widehat X$ に制限したもの(独立集合は $\widehat{\mathcal I}$ の元で $\widehat X$ に含まれるもの)で、(I1)〜(I3)は $\widehat M$ から受け継がれ、階数は lem-mu-sum の $\widehat r$ である。$N_2$ は $\widehat X$ を塊 $\{x\}\times[k]$($x\in X$)に分けた分割マトロイドで、階数は $r_{N_2}(W)=\#\{x\in X\mid W\cap(\{x\}\times[k])\ne\emptyset\}$ である(分割マトロイドは マトロイド交差定理 の節「系」の冒頭にある)。
$J\subseteq\widehat X$ が $N_2$ で独立であることは $\pi$ が $J$ の上で単射であることと同じなので、lem-mu-lift により、$N_1,N_2$ の共通独立集合 $J$ と、$X$ に含まれる和の元 $I$ とは、$I=\pi(J)$、$\lvert I\rvert=\lvert J\rvert$ で対応する(逆向きは prf-mu-lift の $J$ をとる)。よって $\rho(X)$ は共通独立集合の大きさの最大値に等しく、マトロイド交差定理 の定理「マトロイド交差定理」により
$$ \rho(X)=\min_{Z\subseteq\widehat X}\bigl(\widehat r(Z)+r_{N_2}(\widehat X\setminus Z)\bigr) $$
である。この右辺が求める式の右辺に等しいことを示す。
$Y\subseteq X$ について $Z=Y\times[k]$ とおくと、$\widehat r(Z)=\sum_ir_i(Y)$、$r_{N_2}(\widehat X\setminus Z)=\lvert X\setminus Y\rvert$ なので、$Z$ にわたる最小値は $Y$ にわたる最小値以下である。逆に $Z\subseteq\widehat X$ をとり、$Y:=\{x\in X\mid\{x\}\times[k]\subseteq Z\}$ とおく。$Y\times[k]\subseteq Z$ なので(R2)により $\widehat r(Z)\ge\widehat r(Y\times[k])=\sum_ir_i(Y)$ であり、$x\in X\setminus Y$ なら $\{x\}\times[k]$ の写しのどれかが $Z$ の外にあるので $r_{N_2}(\widehat X\setminus Z)=\lvert X\setminus Y\rvert$ である。よって $Z$ での値は $Y$ での値以上であり、2 つの最小値は等しい。$\square$

階数関数の公理

$X\subseteq E$ と $Y\subseteq X$ について $f_X(Y):=\lvert X\setminus Y\rvert+\sum_ir_i(Y)$ とおく。prop-mu-max により $\rho(X)=\min_{Y\subseteq X}f_X(Y)$ である。

階数関数の公理

$\rho$ は マトロイド の命題「階数関数の性質」の(R1)〜(R3)をみたす。

(R1)$f_X(Y)\ge0$ であり、$f_X(\emptyset)=\lvert X\setminus\emptyset\rvert+\sum_ir_i(\emptyset)=\lvert X\rvert$ なので $0\le\rho(X)\le\lvert X\rvert$ である。
(R2)$X\subseteq X'$ とし、$\rho(X')=f_{X'}(Y')$ とする。$Y:=Y'\cap X$ とおくと、各 $r_i$ の(R2)から $r_i(Y)\le r_i(Y')$ であり、$X\setminus Y=X\setminus Y'\subseteq X'\setminus Y'$ である。よって $\rho(X)\le f_X(Y)\le f_{X'}(Y')=\rho(X')$ である。
(R3)$X_1,X_2\subseteq E$ とし、$\rho(X_j)=f_{X_j}(Y_j)$($Y_j\subseteq X_j$)とする。$Y_1\cup Y_2\subseteq X_1\cup X_2$、$Y_1\cap Y_2\subseteq X_1\cap X_2$ である。$Y\subseteq X$ なら $\lvert X\setminus Y\rvert=\lvert X\rvert-\lvert Y\rvert$ であり、$\lvert A\cup B\rvert+\lvert A\cap B\rvert=\lvert A\rvert+\lvert B\rvert$ なので
$$ \lvert(X_1\cup X_2)\setminus(Y_1\cup Y_2)\rvert+\lvert(X_1\cap X_2)\setminus(Y_1\cap Y_2)\rvert=\lvert X_1\setminus Y_1\rvert+\lvert X_2\setminus Y_2\rvert $$
である。各 $r_i$ の(R3)$r_i(Y_1\cup Y_2)+r_i(Y_1\cap Y_2)\le r_i(Y_1)+r_i(Y_2)$ と足し合わせると
$$ \rho(X_1\cup X_2)+\rho(X_1\cap X_2)\le f_{X_1\cup X_2}(Y_1\cup Y_2)+f_{X_1\cap X_2}(Y_1\cap Y_2)\le f_{X_1}(Y_1)+f_{X_2}(Y_2)=\rho(X_1)+\rho(X_2) $$
となる。$\square$

マトロイド和定理

$\mathcal I:=\mathcal I_1\vee\dots\vee\mathcal I_k$ とおく。lem-mu-axioms と マトロイド の定理「マトロイドの公理系の同値」の 2 により、$\mathcal I_\rho:=\{A\subseteq E\mid\rho(A)=\lvert A\rvert\}$ はマトロイドの独立集合の族で、その階数関数は $\rho$ である。$\mathcal I_\rho=\mathcal I$ を示せばよい。
$A\in\mathcal I$ なら、$\rho$ の定義から $\rho(A)\ge\lvert A\rvert$ であり、(R1)と合わせて $\rho(A)=\lvert A\rvert$ である。逆に $\rho(A)=\lvert A\rvert$ なら、$\rho$ の定義から $I\in\mathcal I$ で $I\subseteq A$、$\lvert I\rvert=\lvert A\rvert$ となるものがあり、$I=A$ なので $A\in\mathcal I$ である。よって $\mathcal I=\mathcal I_\rho$ であり、1 が成り立つ。2 は prop-mu-max である。$\square$

和を求める算法

prf-mu-max は、和の最大の元を求める問題を、$k\lvert X\rvert$ 元の集合の上の 2 つのマトロイドの共通独立集合の問題に置き換えている。$\widehat M$ と分割マトロイドの独立性は各 $M_i$ の独立性から判定できるので、マトロイド交差定理 の増加の手続きをそのまま使えば、各 $M_i$ の独立性を問う回数が $k\lvert E\rvert$ の多項式で抑えられる手順で $\rho(E)$ と最大の元が求まる。

系:被覆と詰め込み

$M_1=\dots=M_k=M$(階数関数 $r$)の場合を考える。$M$ の $k$ 個の写しの和を $M^{\vee k}$、その階数関数を $\rho_k$ と書くと、thm-mu-main により $\rho_k(X)=\min_{Y\subseteq X}(\lvert X\setminus Y\rvert+k\,r(Y))$ である。

独立集合による被覆

マトロイド $M=(E,\mathcal I)$ の台集合 $E$ を $k$ 個の独立集合に分割できるための必要十分条件は、すべての $X\subseteq E$ について $\lvert X\rvert\le k\,r(X)$ が成り立つことである。

$E$ が $k$ 個の独立集合に分割できることは、合併の書き直し(def-mu-union の直後)により $E\in\mathcal I^{\vee k}$、つまり $\rho_k(E)=\lvert E\rvert$ と同値である。$\rho_k(E)\le\lvert E\rvert$ はつねに成り立つので、これは「すべての $Y\subseteq E$ で $\lvert E\setminus Y\rvert+k\,r(Y)\ge\lvert E\rvert$」、すなわち「すべての $Y$ で $k\,r(Y)\ge\lvert Y\rvert$」と同値である。$\square$

これは Edmonds の定理である(Edm65a Theorem 1、p. 69 は「$\lvert A\rvert>k\,r(A)$ となる $A$ がない」という形で述べる)。条件の必要性は、$X$ と $k$ 個の独立集合の交わりがそれぞれ $r(X)$ 元以下であることからすぐ分かり、主定理はその十分性を与える。

互いに素な基の詰め込み

マトロイド $M=(E,\mathcal I)$ が互いに素な基を $k$ 個もつための必要十分条件は、すべての $X\subseteq E$ について
$$ k\bigl(r(E)-r(X)\bigr)\le\lvert E\setminus X\rvert $$
が成り立つことである。

互いに素な基 $B_1,\dots,B_k$ があれば $B_1\sqcup\dots\sqcup B_k\in\mathcal I^{\vee k}$ なので $\rho_k(E)\ge k\,r(E)$ である。逆に $\rho_k(E)\ge k\,r(E)$ なら、$\lvert I\rvert\ge k\,r(E)$ の $I\in\mathcal I^{\vee k}$ を互いに素な独立集合の合併 $I_1\sqcup\dots\sqcup I_k$ に書くと、各 $\lvert I_j\rvert\le r(E)$ で和が $k\,r(E)$ 以上なので、すべての $\lvert I_j\rvert=r(E)$ であり、$I_j$ は互いに素な基である。よって $k$ 個の互いに素な基があることは $\rho_k(E)\ge k\,r(E)$ と同値であり、thm-mu-main によりこれは「すべての $X$ で $\lvert E\setminus X\rvert+k\,r(X)\ge k\,r(E)$」と同値である。$\square$

Edm65b Theorem 2(p. 74)は、$E$ を $k$ 個の全域集合(基を含む集合)に分割できる条件として、これと同値な形で述べる。互いに素な基が $k$ 個あれば残りの元を 1 つ目に加えて全域集合の分割が得られ、逆に全域集合はそれぞれ基を含むからである。$\rho_k(E)\le k\,r(E)$($X=E$ ととる)なので、条件の左辺から右辺を引いた量の最大値は $k\,r(E)-\rho_k(E)\ge0$ であり、$k$ 個の互いに素な独立集合の大きさの和の最大値が $k\,r(E)$ にどれだけ足りないかを表す。
連結なグラフ $G=(V,E)$ のグラフ的マトロイドでは、基は全域木であり(マトロイド の命題「グラフ的マトロイド」の直後)、$r(X)=\lvert V\rvert-c(X)$($c(X)$ は $(V,X)$ の連結成分の数)である。このとき cor-mu-pack の条件は $\lvert E\setminus X\rvert\ge k\bigl(c(X)-1\bigr)$ となり、$k$ 本の辺素な全域木の存在条件を与える。cor-mu-cover は辺を $k$ 個の森で覆う条件を与える。頂点の分割による述べ方と、木の交換による直接の証明は Tutte–Nash-Williamsの定理 にある。

例

K5 と垂れ下がる辺

完全グラフ $K_5$ に新しい頂点 $w$ と $K_5$ の頂点を結ぶ辺 $p$ を加えたグラフ $G$(6 頂点、11 辺)のグラフ的マトロイド $M$ をとり、$k=2$ とする。$r(E)=5$ である。$Y=E(K_5)$ では $\lvert E\setminus Y\rvert+2r(Y)=1+2\cdot4=9$、$Y=\emptyset$ では $11$、$Y=E$ では $10$ であり、$\rho_2(E)=9$ である。実際、$K_5$ の辺は 2 本の辺素な全域木($K_5$ の 10 辺のうち 8 辺)までしか森 2 つに入らず、それに $p$ を加えた 9 辺が最大である。

  • cor-mu-pack の条件は $X=E\setminus\{p\}$ で満たされず($2(5-4)=2>1$)、$M$ は互いに素な基を 2 つもたない。実際 $p$ はどの全域木にも含まれる。
  • cor-mu-cover の条件は $X=E(K_5)$ で満たされず($10>2\cdot4$)、$E$ は 2 つの森で覆えない。
    最小値が 9 であることの確かめを開く

    $Y\subseteq E$ をとる。$p\in Y$ なら $Y-p$ に置き換えると $\lvert E\setminus Y\rvert$ が 1 増え、$r$ は 1 減る($p$ は橋なので $r(Y)=r(Y-p)+1$)から値は 1 減る。よって $p\notin Y$ としてよい。$Y\subseteq E(K_5)$ で $(V(K_5),Y)$ の成分の数を $c$ とすると $r(Y)=5-c$ であり、値は $11-\lvert Y\rvert+2(5-c)$ である。$c$ 個の成分の頂点数を $n_1,\dots,n_c$ とすると $\lvert Y\rvert\le\sum_j\binom{n_j}2$ であり、$n_j\ge1$、$\sum_jn_j=5$ のもとで $\sum_j\binom{n_j}2$ は 1 つの成分に頂点を集めたとき最大なので $\lvert Y\rvert\le\binom{6-c}2$ であり、値は $11-\binom{6-c}2+2(5-c)$ 以上である。これは $c=1,2,3,4,5$ でそれぞれ $9,11,12,12,11$ である。$c=1$ で $\lvert Y\rvert=10$、すなわち $Y=E(K_5)$ のとき値は $9$ になる。

ex-mu-uniform の $U_{1,3}\vee U_{1,3}=U_{2,3}$ のように、和の基は各 $M_i$ の基の合併より小さくなることがある($U_{1,3}$ の 2 つの基の合併は 2 元)。$K_4$ のグラフ的マトロイドでは、辺 $12,23,34$ と $13,14,24$ が辺素な全域木なので、2 つの写しの和は 6 辺すべてを独立にもつ自由マトロイドである。

反例

外した仮定・替えた条件反例成り立たなくなる結論
各 $M_i$ がマトロイド(thm-mu-main の 1)$E=\{1,2,3\}$、$\mathcal I_1=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\}\}$(増加公理をみたさない族)、$\mathcal I_2=\{\emptyset\}$$\mathcal I_1\vee\mathcal I_2=\mathcal I_1$ はマトロイドでない
被覆の条件をすべての $X$ ではなく $X=E$ だけで課す(cor-mu-cover)$K_5$ の頂点 $v$ から道 $v\,w_1\,w_2$ を伸ばしたグラフ(7 頂点、12 辺)、$k=2$$\lvert E\rvert=12\le2r(E)=12$ だが、$E$ は 2 つの森に分割できない
詰め込みの条件をすべての $X$ ではなく $X=\emptyset$ だけで課す(cor-mu-pack)ex-mu-k5 の $G$、$k=2$$\lvert E\rvert=11\ge2r(E)=10$ だが、互いに素な基は 2 つない
階数の式の最小を $Y\in\{\emptyset,X\}$ に限る(thm-mu-main の 2)ex-mu-k5 の $G$、$k=2$、$X=E$$\min(11,10)=10$ だが $\rho_2(E)=9$
反例の確かめ

どの行も、右の欄の主張を直接確かめられる。

確かめを開く

1 行目:$\mathcal I_2$ の元は $\emptyset$ だけなので和は $\mathcal I_1$ そのものである。$\{3\}$ に $1$ も $2$ も加えられず($\{1,3\},\{2,3\}\notin\mathcal I_1$)、$\lvert\{3\}\rvert< \lvert\{1,2\}\rvert$ なので(I3)が成り立たない。$\mathcal I_2$ はマトロイド($U_{0,3}$)なので、外した仮定は $\mathcal I_1$ についてだけである。

2 行目:辺は $K_5$ の 10 本と道の 2 本、$r(E)=7-1=6$ である。2 つの森はそれぞれ $K_5$ の辺を $4$ 本以下しか含まない($K_5$ の 5 頂点の上の森)ので、$K_5$ の 10 辺を覆えない。

3 行目:$p$ は橋で、どの全域木にも含まれるので(全域木から $p$ を除くと $w$ が孤立する)、2 つの全域木は $p$ を共有する。

4 行目:$Y=\emptyset$ で $11$、$Y=E$ で $2r(E)=10$ であり、ex-mu-k5 により $\rho_2(E)=9$ である。

関連項目

参考文献

[1]
Jack Edmonds, Minimum partition of a matroid into independent subsets, Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics, 1965, 67–72(Theorem 1 p. 69)
[2]
Jack Edmonds, Lehman's switching game and a theorem of Tutte and Nash-Williams, Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics, 1965, 73–77(Theorem 2 p. 74)
[3]
László Lovász; András Recski, Selected topics of matroid theory and its applications, Rendiconti del Circolo Matematico di Palermo, Serie II, Supplemento, 1982, 171–185(Theorem 6 p. 174)
[4]
James Oxley, What is a matroid?, Cubo, 2003, 179–218。番号と頁は著者による改訂版の Exercise 3.12(p. 13)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する