［参］前原濶・桑田孝泰「グラフ理論とフレームワークの幾何」共立出版

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

　ハードマテリアルの場合，マクスウェルの必要条件：

　　ｅ≧２ｖ−３　　（２次元正方グリッド）

　　ｅ≧３ｖ−６　　（３次元立方グリッド）

　　ｅ≧ｎｖ−ｎ（ｎ＋１）／２　　（ｎ次元立方グリッド）

から，ｍ×ｎの２次元正方グリッドでは，最低でもｍ＋ｎ−１個の筋交いを最適配置に挿入しなければならない．最適配置判定は完全２部グラフＫm,nによって簡単になされる．

　それではグリッドに凹凸があってしかも穴がＨ個あいている場合はどうなるだろうか？　穴の形も四角形とは限らないとする．

　その場合，全体をいくつかの四角形コンパートメントに分けて考えることになるであろうが，結論を先にいうと，必要な筋交い数はグリッドや穴の形に関わらず，

　　上辺＋左辺−１−２Ｈ

になるという．

　すなわち，

　　ｖ−ｅ＋ｆ＝２−２ｇ

の離散版であるが，しかも，最適な筋交い配置も簡単なアルゴリズムとして書ける形になっているのである．

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