■格子上の感染伝搬(その1)

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

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

===================================

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

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

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

===================================

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

===================================

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

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

===================================