Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

最適の二倍を超えないと保証された方法は、保証の無い方法より良い、と思いやすい。本稿は、頂点被覆で二つの方法を、無作為なグラフと作ったグラフの両方で最適と比べる。新しい定理も法則も主張しない。

第一に、保証は守られる。辺を一本ずつ取って両端を入れる方法は、点 $12$ 個の無作為なグラフ $300$ 個のどれでも最適の $2$ 倍を超えず、互いに離れた $6$ 本の辺ではちょうど $2$ 倍になった（第2節）。

第二に、ふつうのグラフでは、保証の無い貪欲が勝つ。辺の確率 $0.2$ で、二倍を保証する方法は平均 $\mathbf{1.680857}$ 倍、辺の多い点から選ぶ貪欲は平均 $\mathbf{1.030833}$ 倍である（第2節）。

第三に、これが本稿の芯である。作ったグラフでは、貪欲が二倍を超える。左に $30$ 点、右に大きさ $2$ から $30$ の塊を並べたグラフで、最適 $30$ 点に対して貪欲は $81$ 点、比 $\mathbf{2.700000}$ である（第3節）。

第四に、同じグラフで、二倍を保証する方法は $2$ 倍にとどまる。$60$ 点、比 $2.000000$ で、保証の範囲に入る（第3節）。

第五に、小さく作ると、まだ貪欲が勝つ。同じ作り方で左を $12$ 点にすると、貪欲は $23$ 点（$1.916667$ 倍）、二倍を保証する方法は $24$ 点（$2.000000$ 倍）である（第3節）。

第六に、分離子は、平均の比を問うか、最悪の比を問うかである。保証は最悪の比についての約束で、ふつうの入力での出来は約束していない（第4節）。

キーワード：頂点被覆、近似比、貪欲法、極大マッチング、最悪の比。

射程（何を示さないか）

新しい定理も法則も主張しない。頂点被覆を求めるのが一般には難しいこと、極大マッチングの両端を取る方法が最適の $2$ 倍を超えないこと、次数の多い点から選ぶ貪欲に定数倍の保証が無いことは、いずれも既知である。難しさの証明に入らない。近似がどこまでできるかの理論には入らない。設計しない。実在の網のどこを見張るべきかは述べない。最適は全部試せる大きさだけで出した。無作為なグラフは点 $12$ 個で全部を試し、作ったグラフは左の点で覆えることと最大マッチングの大きさの二通りで最適を確かめた。既刊との関係：論文348 は、同じグラフで繋ぐのは安く並べるのは高いことを示し、射程注記で近似比には入らないとした。本稿はその席に座る（先客は無い）。ただし巡回の問題ではなく、頂点被覆で近似比を数える。論文633 は、大きい硬貨から払う両替が円なら最少枚数だが旧英貨では一枚多くなることを示した。本稿はその隣にも置く。あちらは貪欲が負ける入力を一つ見せた。ここでは貪欲が平均では勝ち、作った入力で二倍を超えることを並べる。加えたのは、無作為なグラフ $300$ 個で二つの方法の平均と最大を最適と比べたこと、作ったグラフで貪欲が $2.700000$ 倍になると測ったこと、最適を二通りに確かめたこと、分離子を「平均の比か、最悪の比か」に置いたことである。

1. 記法と問い

設定：グラフのすべての辺について、端点の少なくとも一方を含む点の集まりを頂点被覆と呼ぶ。その点の数をできるだけ小さくしたい。二つの方法を比べる。

$$\text{二倍保証}:\ \text{両端がまだ入っていない辺を取り、両端を入れる},\qquad
\text{貪欲}:\ \text{残る辺の最も多い点を入れる}$$

前者は、取った辺が互いに端点を共有しないので、どの被覆もそれぞれから一点を含み、最適の $2$ 倍を超えない。後者にはそのような保証が無い。比は、選んだ点の数を最適の点の数で割った値である。

問い：二倍を保証された方法は、保証の無い方法より良いのか。

2. 無作為なグラフ

計算 2.1：点 $12$ 個、辺の確率を変えて各 $100$ 個のグラフを作り、最適を全部試して出し、二つの方法の比を求めた。

観察 2.2　ふつうのグラフでは、保証の無い貪欲が勝つ。辺の確率 $0.2$ で、二倍保証の方法は平均 $1.680857$ 倍、貪欲は平均 $1.030833$ 倍である。二倍保証の方法は $300$ 個のどれでも $2$ 倍を超えなかったが、最大はちょうど $2.000000$ に届いた。互いに離れた $6$ 本の辺では、最適 $6$ 点に対して $12$ 点で、ちょうど $2$ 倍になる。

3. 作ったグラフ

計算 3.1：左に $k$ 点を置き、右に大きさ $i=2,\dots,k$ の塊を $\lfloor k/i\rfloor$ 個ずつ置いて、右の点を左の $i$ 点と結んだ。左の $k$ 点ですべての辺を覆え、最大マッチングも $k$ 本なので、最適は $k$ 点である。

観察 3.2　これが本稿の芯である。作ったグラフでは、貪欲が二倍を超える。$k=30$ で貪欲は $81$ 点、最適の $2.700000$ 倍を選ぶ。右の大きい塊の点は、いつも左のどの点より辺が多く残るので、貪欲は右の点を次々に選び、左の $30$ 点で済むところを右の点で埋めてしまう。同じグラフで二倍保証の方法は $60$ 点で、保証の範囲にとどまる。

観察 3.3　小さく作ると、まだ貪欲が勝つ。$k=12$ では貪欲 $23$ 点、二倍保証 $24$ 点で、貪欲のほうが一点少ない。同じ作り方でも、貪欲が二倍保証を追い越すのは塊を大きくしてからである。

4. 分離子

観察 4.1　分離子は、平均の比を問うか、最悪の比を問うかである。二倍保証の方法は、どんな入力でも $2$ 倍を超えないという最悪についての約束である。ふつうの入力でどれだけ良いかは約束していない。貪欲は最悪の約束を持たないが、無作為なグラフでは平均 $1.030833$ 倍と最適に近い。どちらが良いかは、平均を問うか最悪を問うかで入れ替わる。

観察 4.2　論文348 の席に座り、論文633 の隣に置く。348 は射程注記で近似比には入らないとした。ここでは頂点被覆で近似比を数え、保証のある比と実際の比を並べた。633 は大きい硬貨から払う貪欲が旧英貨の $48$ ペンスで一枚多くなることを示した。ここでは貪欲が平均では勝ち、作ったグラフで $2$ 倍を超えることを並べた。

観察 4.3　言わないこと。近似の難しさの理論も、実在の網の見張り方も、点 $13$ 個以上の無作為なグラフの最適も扱わない。示したのは、平均の比と最悪の比が別の量で、二つの方法の勝ち負けがそれで入れ替わるということである。

5. 点呼と結び

1. 二倍保証は最適の $2$ 倍以内（第1節）：取った辺が端点を共有しない。
2. $300$ 個のどれも $2$ 倍以内（観察 2.2）：保証は守られる。
3. 離れた $6$ 本でちょうど $2$ 倍（観察 2.2）：$12$ 対 $6$。
4. 二倍保証の平均 $\mathbf{1.680857}$（計算 2.1）：辺の確率 $0.2$。
5. 貪欲の平均 $\mathbf{1.030833}$（計算 2.1）：最適に近い。
6. 作ったグラフで貪欲 $81$ 点（計算 3.1）：最適 $30$ 点。
7. 比 $\mathbf{2.700000}$（観察 3.2）：本稿の芯。
8. 同じグラフで二倍保証 $60$ 点（計算 3.1）：$2$ 倍。
9. $k=12$ では $23$ 対 $24$（観察 3.3）：まだ貪欲が勝つ。
10. 平均の比か、最悪の比か（観察 4.1）：分離子・論文348 の席・論文633。

結び：頂点被覆では、二倍を保証する方法がふつうのグラフで貪欲に負け、作ったグラフでは貪欲が二倍を超える。点 $12$ 個・辺の確率 $0.2$ の無作為なグラフでは、二倍保証の方法が平均 $1.680857$ 倍、辺の多い点から選ぶ貪欲が平均 $1.030833$ 倍である。二倍保証の方法は辺の両端を必ず入れるので、ふつうのグラフでは片方で足りる点まで入れてしまうからである。左に $30$ 点、右に大きさの違う塊を並べたグラフでは、最適 $30$ 点に対して貪欲が $81$ 点（$2.700000$ 倍）、二倍保証の方法は $60$ 点にとどまる。保証は最悪の比についての約束で、平均の出来は約束していない。既刊との位置：論文348 が射程注記で空けた近似比の席に頂点被覆で座り、論文633 の貪欲の隣に、平均と最悪で勝ち負けが入れ替わる例を置いた。正直に言えば、無作為なグラフは点 $12$ 個だけで、作ったグラフは一つの作り方だけである。

参考文献

1. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
2. Vazirani, V. V. (2001). Approximation Algorithms. Springer.
3. 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. YOI: https://www.yamagishiyuuki.com/yoi/348 ・ DOI: 10.5281/zenodo.22683555
4. 山岸勇輝 (2026). 『大きい硬貨から払う両替は、円なら必ず最少枚数だが、旧英貨では 48 ペンスで一枚多くなる』[論文633]. YOI: https://www.yamagishiyuuki.com/yoi/633 ・ DOI: 10.5281/zenodo.23014568

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「頂点被覆の二倍保証の方法は、ふつうのグラフでは貪欲に負け、作ったグラフでは貪欲が二倍を超える」［論文875］. YOI: https://www.yamagishiyuuki.com/yoi/875

@misc{yamagishi2026yoi875,
  author = {Yamagishi, Yuuki},
  title = {For Vertex Cover, the Twice-Guaranteed Method Loses to Greed on Ordinary Graphs, and Greed Exceeds Twice on a Built One},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/875},
  note = {Preprint, edition 1}
}