隣接２拠点による感染伝搬を考える

ｎ×ｎ格子のｎ^2個の拠点すべてに感染するのに必要な感染拠点の最小個数はｎである。=対角線上のすべての拠点

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

感染したマスを黒く塗る。

２個の感染したマスに隣接するマスが感染するとき、周長は増加しない。＝不変量

最終的にｎ×ｎ格子全体が感染したときその周長は4ｎなので、少なくともｎ個の感染したマスが必要であることが分かる。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｋ×ｌ長方形格子ですべての拠点に感染するためには少なくとも[(k+l)/2]個の感染拠点が必要である。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｄ次元立方格子ですべての拠点に感染するためには少なくとも[d(n-1)/2]+1個の感染拠点が必要である。

n1・n2・・・ndのｄ次元長方格子ですべての拠点に感染するためには少なくとも[(Σ(ni-d+2)/2]個の感染拠点が必要である。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

トーラス上のｎ×ｎ格子のｎ^2個の拠点すべてに感染するのに必要な感染拠点の最小個数はｎ-１である。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝