ユニモジュラ行列
行 R および列 C=st の成分を計算するために、T 内の s から t への路 P に着目する。このとき、その成分は次のように決定される:
弧 R が P において前方に向いているなら、+1;
弧 R が P において後方に向いているなら、-1;
弧 R が P に現れないなら、0.
詳細については、Schrijver (2003) を参照されたい。
5. Ghouila-Houri は、ある行列が全ユニモジュラ行列であるための必要十分条件は、行の全ての部分集合 R に対して、行に符号を割り当てる関数 s : R → ± 1 {\displaystyle s:R\to \pm 1} でその和 ∑ r ∈ R s ( r ) r {\displaystyle \sum _{r\in R}s(r)r} (これは、その考えている行列と等しい幅を持つ行ベクトル)が { 0 , ± 1 } {\displaystyle \{0,\pm 1\}} に全ての成分を持つようなものが存在すること(すなわち、その行部分行列が高々一つの discrenpacy を持つこと)であることを証明した。このことと、他のいくつかの同値性のための条件は、Schrijver (2003) において示されている。
6. Hoffman と Kruskal は、次の定理を証明した。