０／１多面体とは，すべての頂点の座標が０か１である多面体で，立方体の頂点の部分集合の凸包のことである．持ち得るファセットの最大数ｆは

　　２^n≦ｆ≦ｎ！＋２ｎ

で，上界と下界の間には非常に大きなギャップがある．今回のコラムでは０／１多面体の仲間たちを紹介したい．

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

【１】割当多面体

　たとえば，４×４置換行列（各行各列の成分に１がちょうど１つ現れ，他の成分が０の行列），

　　［０，１，０，０］

　　［０，０，０，１］

　　［１，０，０，０］

　　［０，０，１，０］

のなす空間を１６次元空間と思うと各行列は０／１ベクトルとなり，その凸包は０／１多面体となる．

　ｎ次正方行列Ｍは，

［１］各成分が非負で，各行角列の和が１のとき，２重確率行列

［２］各行各列の成分に１がちょうど１つ現れ，他の成分が０のとき，置換行列

と呼ばれる．また，前述の４×４置換行列は完全２部グラフＫ4,4の完全マッチングと対応する．

　一方，任意の２重確率行列は，置換行列の凸結合で表現されることが，バーコフとフォン・ノイマンによって独立に示されている．そのため，２重確率行列全体は置換行列を端点とする凸多面体となり，割当多面体（バーコフ多面体，完全マッチング多面体，２重確率多面体）と呼ばれる．

　この多面体はｎ！個の頂点とｎ^2個のファセットをもつ（ｎ−１）^2次元の多面体である．割当多面体と置換多面体の間には射影写像がある．

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

【２】巡回セールスマン多面体

　巡回セールスマン問題とはｎ頂点の完全グラフＫnのすべての頂点を回って戻ってくる最短ハミルトン経路を問う問題である．

　置換行列が完全２部グラフＫn,nと対応するのに対して，巡回セールスマン多面体は完全グラフＫnに対応している．

　この多面体は（ｎ−１）！／２個の頂点をもつnＣ2−ｎ＝ｎ（ｎ−３）／２次元の多面体である．

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