§E16.28近似アルゴリズム

証明.$\mathcal A$を$\rho$-近似アルゴリズムとし、$\mathrm{OPT}(I)>0$を満たすインスタンス$I$をとる。$\mathcal A(I)\in F(I)$であるから、最適値が最小値であることにより$\mathrm{OPT}(I)\le\mathrm{cost}_I\bigl(\mathcal A(I)\bigr)$である。近似比の定義とあわせて

を得る。両端を$\mathrm{OPT}(I)>0$で割ると$1\le\rho$である。▨

証明. ループ不変条件（§D2.8 定義 1.1）として「$M$は$G$のマッチングであり$M\subseteq E$である」をとる。初期化では$M=\emptyset$がマッチングであるから成り立つ。維持については、本体は$M\cup\{e\}$がマッチングである場合にだけ$e$を加えるので、実行後も$M$はマッチングである。

停止性を示す。$\varphi=m-\lvert M\rvert$と置く。不変条件により$M\subseteq E$であるから$\lvert M\rvert\le m$であり、$\varphi$は非負整数である。本体を一度実行すると$\lvert M\rvert$が$1$増えるので$\varphi$は狭義に減少する。§D2.8 命題 1.4により手続きは有限回で停止し、$\varphi$の初期値が$m$であるから反復回数は$m$以下である。

終了を確かめる。停止時にはループの継続条件が偽であり、$M\cup\{e\}$がマッチングとなる辺$e\in E\setminus M$は存在しない。ここで$M\subsetneq M'$を満たすマッチング$M'$が存在すると仮定し、$e\in M'\setminus M$をとる。$M\cup\{e\}\subseteq M'$であり、マッチングの部分集合はマッチングである（部分集合の相異なる二辺はもとの集合の相異なる二辺でもあるから端点を共有しない）ので、$M\cup\{e\}$はマッチングであり$e\in E\setminus M$である。これは継続条件が偽であることに反する。よって停止時の$M$は極大なマッチングである。この形の議論が正当性を与えることは§D2.8 定理 1.2による。▨

証明.$C$は頂点被覆であるから、$M$の各辺$e$は少なくとも一方の端点を$C$にもつ。$M$は有限集合であるから、各$e\in M$について$C$に属する端点を一つ選び、それを$\psi(e)$と書く。これにより写像$\psi:M\to C$が定まる。

$\psi$が単射であることを示す。$e,e'\in M$が$e\ne e'$かつ$\psi(e)=\psi(e')$を満たすと仮定する。$\psi(e)$は$e$の端点であり、$\psi(e')$は$e'$の端点であるから、$e$と$e'$は頂点$\psi(e)$を共有する。これは$M$がマッチングであることに反する。よって$\psi$は単射であり$\lvert M\rvert\le\lvert C\rvert$である。

$C$を頂点数が最小の頂点被覆にとると$\lvert C\rvert=\tau(G)$であるから$\lvert M\rvert\le\tau(G)$を得る。▨

証明. 頂点被覆であること。辺$e=uv\in E$をとり、$u\notin C(M)$かつ$v\notin C(M)$であると仮定する。$C(M)$の定め方により、$M$のどの辺も$u$を端点にもたず、$v$も端点にもたない。したがって$e$は$M$のどの辺とも端点を共有しない。とくに$e\notin M$である（$e\in M$ならば$u\in C(M)$となる）。

$M\cup\{e\}$がマッチングであることを確かめる。$M\cup\{e\}$の相異なる二辺$f,f'$をとる。ともに$M$に属するならば、$M$がマッチングであることから端点を共有しない。一方が$e$で他方が$M$の辺ならば、上に述べたとおり端点を共有しない。よって$M\cup\{e\}$はマッチングであり、$e\notin M$より$M\subsetneq M\cup\{e\}$である。これは$M$の極大性に反する。

したがって$E$のすべての辺は少なくとも一方の端点を$C(M)$にもち、$C(M)$は頂点被覆である。

頂点数。各辺$e\in M$に対し、その端点の集合を$\iota(e)$と書く。$G$は単純でありループをもたないので$\lvert\iota(e)\rvert=2$である。$C(M)=\bigcup_{e\in M}\iota(e)$である。$M$の相異なる二辺は端点を共有しないので、$e\ne e'$ならば$\iota(e)\cap\iota(e')=\emptyset$である。よってこの合併は互いに交わらない集合の合併であり、和の法則（§D2.2 定理 2.1）により

である。▨

証明.補題 2.6により$C(M)$は頂点被覆であり$\lvert C(M)\rvert=2\lvert M\rvert$である。

$M$はマッチングであるから、補題 2.5により$\lvert M\rvert\le\tau(G)$である。両辺を$2$倍して$2\lvert M\rvert\le2\tau(G)$を得る。二つを合わせて主張が従う。▨

証明.命題 2.4の停止性と極大性の証明は、加えることのできる辺が複数あるときにどれを選ぶかに依存しない。よって選び方をどのように固定しても手続きは停止し、出力される$M$は極大なマッチングである。定理 2.7により$C(M)$は頂点被覆、すなわち定義 2.1の意味の実行可能解であり、

が成り立つ。これは定義 1.2の意味で$\rho=2$の場合の条件である。▨

証明.主張 (1)を示す。$R\ne\emptyset$とし$e\in R$をとる。$R\subseteq U=\bigcup_{j\in J}S_j$であるから$e\in S_j$を満たす$j\in J$が存在し、その$j$について$S_j\cap R\ne\emptyset$である。よって候補となる添字の集合は空でない。$J$は有限集合であるから、その中で比を最小にする添字が存在する。

主張 (2)を示す。ループの状態に対して変量$\lvert R\rvert$をとる。これは非負整数である。選んだ$j^{*}$について$S_{j^{*}}\cap R\ne\emptyset$であるから、$R\setminus S_{j^{*}}$は$R$の真部分集合であり$\lvert R\rvert$は狭義に減少する。§D2.8 命題 1.4により手続きは有限回で停止し、$\lvert R\rvert$の初期値が$\lvert U\rvert$であるから反復回数は$\lvert U\rvert$以下である。

主張 (3)を示す。ループ不変条件（§D2.8 定義 1.1）として「$R\subseteq U$かつ$U\setminus R=\bigcup_{j\in\mathcal C}S_j$」をとる。初期化では$R=U$かつ$\mathcal C=\emptyset$であり、両辺とも空集合である。維持については、$j^{*}$を加えた後の$\mathcal C'=\mathcal C\cup\{j^{*}\}$と$R'=R\setminus S_{j^{*}}$に対し、$S_{j^{*}}\subseteq U$であることから

であり、不変条件が保たれる。停止時には継続条件が偽であり$R=\emptyset$であるから、不変条件より$U=\bigcup_{j\in\mathcal C}S_j$、すなわち$\mathcal C$は被覆である。この形の議論が正当性を与えることは§D2.8 定理 1.2による。

主張 (4)を示す。ある反復で課金される要素は$S_{j^{*}}\cap R$の要素であり、その反復の終わりに$R$から取り除かれる。$R$は反復のたびに減るだけであるから、一度取り除かれた要素は以後の反復の$R$に属さず、再び課金されることはない。また 3 の停止時の条件$R=\emptyset$と不変条件により、すべての要素はいずれかの反復で$R$から取り除かれ、そのとき課金される。よって各要素はちょうど一度課金される。

主張 (5)を示す。まず、各反復で選ばれる添字は互いに相異なる。ある反復で$j^{*}$が選ばれると、その反復の終わりに$R$から$S_{j^{*}}$が取り除かれて$S_{j^{*}}\cap R=\emptyset$となり、$R$は以後も減るだけであるから、$j^{*}$が再び候補になることはないからである。したがって反復の回数は$\lvert\mathcal C\rvert$に等しく、

である。各反復について、その反復で課金される要素の個数は$\lvert S_{j^{*}}\cap R\rvert$であり、各要素への課金額は$w_{j^{*}}/\lvert S_{j^{*}}\cap R\rvert$であるから、その反復で課金された額の総和は

である。反復について加え、4 により各要素がちょうど一度課金されることを用いると$w(\mathcal C)=\sum_{e\in U}\mathrm{price}(e)$を得る。▨

証明. はじめに$\mathrm{OPT}(I)>0$を確かめる。$U$は空でないので、どの被覆$\mathcal C$も空でなく、$w_j>0$より$w(\mathcal C)>0$である。よって最適値も正である。

$1\le l\le k$を固定し、$e_l$が課金された反復の開始時における$R$の値を$R_l$と書く。

$\lvert R_l\rvert\ge k-l+1$であること。$l\le l'\le k$をとる。命題 3.4 (4)により各要素はちょうど一度課金され、$e_{l'}$が課金されるのは$e_l$が課金される反復と同じか、それより後の反復である。同じ反復ならば$e_{l'}\in S_{j^{*}}\cap R_l\subseteq R_l$である。より後の反復ならば、その反復の開始時の$R$に属し、$R$は反復のたびに減るだけであるから$e_{l'}\in R_l$である。$e_l,e_{l+1},\dots,e_k$は相異なる$k-l+1$個の要素であるから$\lvert R_l\rvert\ge k-l+1$である。

比の小さい集合が最適な被覆の中に存在すること。$\mathcal O\subseteq J$を$w(\mathcal O)=\mathrm{OPT}(I)$を満たす被覆とし、

と置く。$\mathcal O$は$U$を覆い$R_l\subseteq U$であるから、$R_l$の各要素は少なくとも一つの$j\in\mathcal O$について$S_j\cap R_l$に属する。したがって

が成り立つ。左辺は$R_l$の各要素を少なくとも一度数えているからである。$R_l\ne\emptyset$であるから、この不等式より$\mathcal O_l\ne\emptyset$である。

すべての$j\in\mathcal O_l$について

が成り立つと仮定する。両辺に$\lvert S_j\cap R_l\rvert>0$を掛けると$w_j>\dfrac{\mathrm{OPT}(I)}{\lvert R_l\rvert}\lvert S_j\cap R_l\rvert$である。$j\in\mathcal O_l$について加え、$j\in\mathcal O\setminus\mathcal O_l$については$\lvert S_j\cap R_l\rvert=0$かつ$w_j>0$であることを用いると

となる。ここで最後の不等号には$\mathrm{OPT}(I)>0$と上で示した$\sum_{j\in\mathcal O}\lvert S_j\cap R_l\rvert\ge\lvert R_l\rvert$を用いた。両端を比べると$\mathrm{OPT}(I)>\mathrm{OPT}(I)$となり矛盾する。よって$j_0\in\mathcal O_l$が存在して

が成り立つ。

結論。$e_l$が課金された反復で選ばれた添字を$j^{*}$とする。$j_0$は$S_{j_0}\cap R_l\ne\emptyset$を満たすので、その反復における候補である。手続きは候補の中で比を最小にする添字を選ぶので

である。最後の不等号は$\lvert R_l\rvert\ge k-l+1$と$\mathrm{OPT}(I)>0$による。▨

証明.命題 3.4 (3)により$\mathcal C$は被覆であり、5 により

である。ここで$e_1,\dots,e_k$は補題 3.5のとおり課金された順に並べた$U$の要素である。同補題を各項へ適用すると

である。和の添字を$i=k-l+1$と置き換えると、$l$が$1$から$k$まで動くとき$i$は$k$から$1$まで動くので

である。よって$w(\mathcal C)\le H_k\,\mathrm{OPT}(I)$を得る。▨

証明.命題 3.4と補題 3.5の証明は、比を最小にする添字が複数あるときにどれを選ぶかに依存しない。よって定理 3.6は、選び方をどのように固定した場合についても成り立つ。

この族に属するインスタンス$I$をとり、その台集合の要素数を$k$とすると$k\le K$である。定理 3.6により$w(\mathcal C)\le H_{k}\,\mathrm{OPT}(I)$である。調和数は$k\le K$のとき$H_{k}\le H_K$を満たす。実際、$H_K-H_{k}=\sum_{i=k+1}^{K}1/i\ge0$である。よって$w(\mathcal C)\le H_K\,\mathrm{OPT}(I)$であり、定義 1.2の意味で$\rho=H_K$の場合の条件が成り立つ。

すべての費用が$1$である場合は$w(\mathcal C)=\lvert\mathcal C\rvert$であり、被覆の費用はその集合の個数に等しいので、最後の主張が従う。▨