グラフとは頂点と頂点を結ぶ辺の集まりであり, 辺によって結ばれた2つの頂点は隣接していると呼ぶことを思い出そう.
グラフはユークリッド空間上の点を頂点として関連付けることでユークリッド空間に埋め込むことができる. ( 訳注 : ある空間内にグラフを表現することをグラフの埋め込みと言う. )
柔軟なグラフ (flexible graph) とは, 隣接する頂点間のそれぞれの距離を一定に保ったまま, 少なくとも2つの隣接していない頂点間の距離が変化するように, ひとつ以上の頂点を連続的に動かすことが可能なグラフの埋め込みのことである.
剛なグラフ (rigid graph) とは柔軟でないグラフの埋め込みのことである.
平たく言えば, もし頂点を360度回転するヒンジに, 辺を曲がらない非弾性の棒に置き換えたとき, グラフの残りの部分から独立して動かすことのできる部分がないグラフは剛なグラフである.
ユークリッド平面に埋め込まれた格子グラフは下記のアニメが示すように剛性を持たない:
#ref(): File not found: "p434_rigid.gif" at page "Problem 434"
しかしながら, いくつかのセルに対角線の辺を追加することで剛性を持たせることができる. 例として, 2x3 の格子グラフの場合, グラフを剛性にする19通りの方法がある:
#ref(): File not found: "p434_rigid23.png" at page "Problem 434"
この問題の目的から鑑みて, 格子グラフに剛性を持たせる別の方法として, 対角線の辺の向きを変えたり, 1つのセルに2つの対角線の辺を追加したりすることは考慮しない.
m × n の格子グラフに剛性を持たせる方法の数を R(m, n) で表す.
例として, R(2,3) = 19, そして R(5,5) = 23679901.
1 ≤ i,j ≤ N における ΣR(i, j) を S(N) と定義しよう.
例として, S(5) = 25021721.
S(100) を求め, 1000000033 を法として答えよ.