グラフの完全マッチングとは辺の部分集合Mで、グラフの各頂点が ただひとつのMの元の端点になっているものです。例えば和室に畳を敷き詰めること は正方格子グラフの完全マッチングを定めることに対応しています。近年、統計力学 のダイマー模型の理論が急速に発展しているようですが、数値実験の果たした役割は 大変大きかったと想像されます。ダイマーのランダム配置を高速にシミュレートする 方法は数値実験で重要であるだけでなく、理論的にも興味深いものです。 R. KenyonとS. Sheffieldによる平面2部グラフの完全マッチングの高速なランダムサン プリング法を計算機実験の結果とあわせて紹介します。 次の 図 は数値実験の様子を描いたものです。