7.4 最小スパニング木 連結な無向グラフの全ての頂点を含む部分グラフで木であるものをスパニング木という。 行列木定理 連結な無向グラフGのスパニング木の個数はL(G)*1の任意の対角要素に関する余因子の値に等しい。 重み付きグラフの重みを最も小さくする…

連言・選言標準形 以下の議論では限量子を含むものは考えない 連言標準形 (P1 ∨ P2)∧(P3 ∨ P4)∧(P5 ∨ P6)のように、∨で結合した節(clause)を∧で結合した形。 選言標準形 (P1 ∧ P2)∨(P3 ∧ P4)∨(P5 ∧ P6)のように、∧で結合したもの（特に名前はない）を∨で結合…