§E16.17マトロイドと貪欲法

(1)を示す。手続きの各反復で行う判定は$I_{i-1}\cup\{e_i\}\in\mathcal I$だけであるから、出力は並べ方$e_1,\dots,e_n$と$\mathcal I$だけで定まり、重みの値によらない。$E=\emptyset$のときは基底が$\emptyset$だけであり、出力も$\emptyset$であるから、主張が成り立つ。以下$E\ne\emptyset$とし、§E16.15 命題 2.3による基底の共通の濃度を$b$と書く。

前半を示す。$c=\max\{0,\ -\min_{x\in E}w(x)\}$と置き、$w'(x)=w(x)+c$と定める。$c\ge0$かつすべての$x\in E$について$c\ge-w(x)$であるから、$w'$は非負重みである。$w'(e_1)\ge\dots\ge w'(e_n)$であるから、$e_1,\dots,e_n$は$w'$に対する処理順であり、出力$G$は$w'$に対するこの処理順の貪欲解である。定理 4.1より$G$は基底であり、すべての基底$B$について$w'(B)\le w'(G)$を満たす。基底$B$について$w'(B)=w(B)+bc$であるから、$w(B)+bc\le w(G)+bc$、すなわち$w(B)\le w(G)$である。

後半を示す。$W=\max_{x\in E}w(x)$と置き、$w''(x)=W-w(x)$と定める。$w''$は非負重みであり、$w(e_1)\le\dots\le w(e_n)$から$w''(e_1)\ge\dots\ge w''(e_n)$が従うので、$e_1,\dots,e_n$は$w''$に対する処理順である。前半と同じく、出力$G'$は基底であり、すべての基底$B$について$w''(B)\le w''(G')$を満たす。基底$B$について$w''(B)=bW-w(B)$であるから、$bW-w(B)\le bW-w(G')$、すなわち$w(G')\le w(B)$である。この議論では基底の濃度が一定であることを用いたので、比較の相手を基底に限れば重みの符号に条件は要らない。比較の相手を独立集合全体に広げると非負性が要ることは、(4)で確かめる。

(2)を示す。$p=\lvert E_t\rvert$と置く。$E_t=\{e_1,\dots,e_p\}$であることを示す。$e_i\in E_t$かつ$i'<i$ならば、処理順の条件より$w(e_{i'})\ge w(e_i)\ge t$であるから$e_{i'}\in E_t$である。ゆえに$E_t$の元の添字の集合は、ある番号以下の正の整数の全体であり、その個数は$p$であるから、$E_t=\{e_1,\dots,e_p\}$である。

第$i$反復で採用されうる元は$e_i$だけであるから、$I_p$は$G$の元のうち$e_1,\dots,e_p$のいずれかであるものの全体であり、$G\cap E_t=I_p$である。命題 2.2の証明の不変条件より$I_p\in\mathcal I$であり、$I_p\subseteq E_t$である。$I_p$の極大性を示す。$x\in E_t\setminus I_p$が$I_p\cup\{x\}\in\mathcal I$を満たすと仮定し、$x=e_i$（$1\le i\le p$）と書く。手続きは$I_0\subseteq I_1\subseteq\dots\subseteq I_n$を満たすから$I_{i-1}\subseteq I_p$であり、$I_{i-1}\cup\{e_i\}\subseteq I_p\cup\{x\}$である。条件 (I2)より$I_{i-1}\cup\{e_i\}\in\mathcal I$であるから、第$i$反復で$e_i$が採用され、$e_i\in I_i\subseteq I_p$となって$x\notin I_p$に反する。したがって$G\cap E_t$は$\{I\in\mathcal I:\ I\subseteq E_t\}$の極大な元であり、§E16.16 命題 4.2より$\lvert G\cap E_t\rvert=r(E_t)$である。

後半を示す。$B$を基底とする。§E16.15 系 2.4より$\lvert B\rvert$は独立集合の濃度の最大値であるから$\lvert B\rvert=r(E)\ge1$であり、$B\ne\emptyset$である。$t=\min_{x\in B}w(x)$と置く。$B\subseteq E_t$であり、$B$は$E_t$に含まれる独立集合であるから$r(E_t)\ge\lvert B\rvert$である。命題 2.2より$G$は基底であり、§E16.15 命題 2.3より$\lvert G\rvert=\lvert B\rvert$である。ゆえに$\lvert G\cap E_t\rvert=r(E_t)\ge\lvert G\rvert$であり、$G\cap E_t\subseteq G$と合わせて$G\cap E_t=G$、すなわち$G\subseteq E_t$である。したがって$G$のすべての元の重みは$t$以上であり、$\min_{x\in G}w(x)\ge t=\min_{x\in B}w(x)$である。

(3)を示す。処理順を一つ選んでその貪欲解を$G$とし、$G$の元を採用した順に$g_1,\dots,g_r$と書く。定理 4.1より、$G$は重みが最大の基底である。$B$を重みが最大の基底とし、その元を重みの降順に$b_1,\dots,b_s$と並べる。§E16.15 命題 2.3より$s=r$である。補題 3.1を$A=B$へ適用すると、$1\le j\le r$を満たすすべての$j$について$w(g_j)\ge w(b_j)$である。$G$と$B$はともに重みが最大の基底であるから$w(G)=w(B)$であり、

である。各項は非負であるから、すべての$j$について$w(b_j)=w(g_j)$である。ゆえに列$(w(b_1),\dots,w(b_r))$は$(w(g_1),\dots,w(g_r))$に等しく、$B$の選び方によらない。

$w$が単射であるとする。等式$w(b_j)=w(g_j)$と単射性より、$1\le j\le r$を満たすすべての$j$について$b_j=g_j$であるから、$B=G$である。ゆえに重みが最大の基底は$G$ただ一つである。

例を作る。$U_{1,2}$の台集合を$E=\{1,2\}$とし、$w(1)=w(2)=1$とする。§E16.15 命題 5.2より基底は$\{1\}$と$\{2\}$であり、どちらの重みも$1$であるから、重みが最大の基底は二つある。

(4)では、$U_{1,2}$の台集合を$E=\{1,2\}$とする。独立集合は$\emptyset$、$\{1\}$、$\{2\}$である。負の値を許した重み$w(1)=-1$、$w(2)=-2$を与え、定義 2.1の手続きをそのまま実行する。処理順は$w(1)>w(2)$より$1,2$に定まる。$\{1\}$は独立であるから$1$を採用し、$\{1,2\}$は独立でないから$2$を採用しない。貪欲解は$G=\{1\}$であり、$w(G)=-1$である。一方、$\emptyset$は独立集合であり$w(\emptyset)=0>-1$であるから、$G$は重み最大の独立集合ではない。本文の評価にあてはめると、$A=\emptyset$では$s=0$、$r=1$であり、二つ目の不等号$\sum_{j=1}^{0}w(g_j)\le\sum_{j=1}^{1}w(g_j)$は$0\le-1$となって成り立たない。この不等号が、非負性を用いた箇所である。

(5)では、$\varepsilon$を一般の実数として、証明と同じ処理順に対する貪欲解を考える。$A$の元をすべて先に走査する処理順が定義 2.1の条件を満たすには$1+\varepsilon\ge1$、すなわち$\varepsilon\ge0$が要る。$\varepsilon\ge0$のとき、証明と同じ計算により

である。

$\varepsilon=1$とすると$w(G)=2a$、$w(B)=b+k$である。証明が用いることができるのは$b\ge a+1$と$0\le k\le a$だけであり、$b=a+1$、$k=0$のとき$w(B)-w(G)=1-a$となる。とくに例 5.2の$A=\{3\}$、$B=\{1,2\}$では$a=1$、$b=2$、$k=0$であり、$\varepsilon=1$の重みは$w(3)=2$、$w(1)=w(2)=1$である。このとき$w(G)=w(\{3\})=2$、$w(B)=2$であり、$w(B)>w(G)$が成り立たないので、矛盾は得られない。

破綻しない範囲を求める。仮定のもとで$a\ge1$である。実際、$a=0$ならば$A=\emptyset$であり、$b\ge1$より$x\in B$を取ると$\{x\}\subseteq B\in\mathcal I$から$A\cup\{x\}=\{x\}\in\mathcal I$となって仮定に反する。$0\le\varepsilon<1/a$ならば、$b\ge a+1$と$k\varepsilon\ge0$より

であり、証明は成立する。逆に$\varepsilon\ge1/a$のとき、証明が破綻する有限独立集合系がある。$\lvert A\rvert=a$、$\lvert B\rvert=a+1$、$A\cap B=\emptyset$とし、$E=A\cup B$、$\mathcal I=2^{A}\cup2^{B}$と置く。$(E,\mathcal I)$は有限独立集合系であり、$x\in B$に対して$A\cup\{x\}$は$A$にも$B$にも含まれないから$\mathcal I$に属さない。このとき$k=0$、$b=a+1$であり、$w(G)=a+a\varepsilon\ge a+1=w(B)$となって、$w(B)>w(G)$は得られない。$\varepsilon<0$のときは、$A$の元の重み$1+\varepsilon$が$B\setminus A$の元の重み$1$より小さいので、$A$の元を先に走査する処理順を取ることができない。ゆえに、どの$A,B$に対しても証明が成立する$\varepsilon$の範囲は$0\le\varepsilon<1/a$である。$\varepsilon=\dfrac{1}{a+1}$はこの範囲に属し、$\varepsilon=1$は$a\ge1$より$1\ge1/a$を満たすので属さない。

(6)を示す。§E16.15 定義 1.1 条件 (I3)が成り立たないと仮定し、本文と同じく$A,B\in\mathcal I$、$a=\lvert A\rvert<b=\lvert B\rvert$、$k=\lvert A\cap B\rvert$とする。$n=\lvert E\rvert$、$m=\lvert B\setminus A\rvert=b-k$、$R=E\setminus(A\cup B)$、$t=\lvert R\rvert$と置き、$A=\{x_1,\dots,x_a\}$、$B\setminus A=\{y_1,\dots,y_m\}$、$R=\{z_1,\dots,z_t\}$と書く。$a+m+t=n$である。$\delta$を

を満たす実数とし、重みを

と定める。$y_1$の重みが$1-\delta$である。

重みが非負で相異なり、$A$の元、$B\setminus A$の元、$R$の元の順に真に小さくなることを確かめる。各集合の中では添字ごとに値が異なる。$A$の元の重みは$1$より大きく、$B\setminus A$の元の重みは$1$より小さい。$m+t\le n\le n^2$より$(m+t)\delta<1$であるから、$B\setminus A$の元の重みの最小値$1-m\delta$は$R$の元の重みの最大値$t\delta$より大きい。$R$の元の重みは正である。ゆえに処理順はただ一つに定まり、$A$の元、$B\setminus A$の元、$R$の元の順に走査する。

この処理順に対する貪欲解$G$は、本文と同じ議論により、$A$の走査を終えた時点で$A$に等しく、$B\setminus A$の元を一つも採用しない。$R$の元のうち採用されたものの集合を$S$と書くと$G=A\cup S$であり、$w(G)\le w(A)+w(R)$である。$w(B)=w(A\cap B)+w(B\setminus A)$と$w(A)=w(A\cap B)+w(A\setminus B)$より