全ユニモジュラ性
が全
, または 
となることである. 全ユニモジュラ性とは, 全
全ユニモジュラ性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/20 23:47 UTC 版)
「ユニモジュラ行列」の記事における「全ユニモジュラ性」の解説
全ユニモジュラ行列（totally unimodular matrix, TU 行列）とは、その非特異なすべての正方部分行列がユニモジュラ行列であるような行列のことを言う。したがって、全ユニモジュラ行列は、必ずしもそれ自身が正方行列でなくてもよい。定義より、任意の全ユニモジュラ行列の成分は 0、+1 あるいは −1 でしかあり得ないことが分かる。 全ユニモジュラ行列は、ある線型計画が整数計画であることを確かめるための迅速な方法を提供するため、多面体的組合せ論（英語版）や組合せ最適化において極めて重要な概念となる。特に、A が全ユニモジュラ行列で b を整数ベクトルとしたとき、 { min c x ∣ A x ≥ b , x ≥ 0 } {\displaystyle \{\min cx\mid Ax\geq b,x\geq 0\}} あるいは { max c x ∣ A x ≤ b } {\displaystyle \{\max cx\mid Ax\leq b\}} のような形状の線型計画は、任意の c に対して、整数の最適解を持つ。したがって、A が全ユニモジュラ行列で b が整数ベクトルであるなら、実行可能領域（例えば、 { x ∣ A x ≥ b } {\displaystyle \{x\mid Ax\geq b\}} ）のすべての極値点は整数であり、したがってその実行可能領域は整数多面体となる。
※この「全ユニモジュラ性」の解説は、「ユニモジュラ行列」の解説の一部です。
「全ユニモジュラ性」を含む「ユニモジュラ行列」の記事については、「ユニモジュラ行列」の概要を参照ください。
- 全ユニモジュラ性のページへのリンク
