この記事について
前回の記事「整数性を持つ整数計画問題 ─ 完全単模行列が教えてくれること」で「無向グラフの接続行列は、グラフが奇閉路を含む場合に TU でなくなる」と書きました。例として三角形 $K_3$ を挙げましたが、なぜ TU でなくなるのか直感が湧きにくいかもしれません。
この記事では $K_3$ の接続行列の行列式を実際に計算しながら、奇閉路と TU 性の関係を確かめてみます。
K₃（三角形）の接続行列を実際に作ってみる
K₃ は「3つの頂点が全てつながっている」グラフ（三角形）です。
1
/ \
/ \
2-----3
- 頂点：$1, 2, 3$
- 辺：$e_1 = {1,2},\ e_2 = {2,3},\ e_3 = {1,3}$
無向グラフの接続行列は「頂点 $v$ が辺 $e$ の端点なら $1$、そうでなければ $0$」（有向グラフのように $+1, -1$ にはならない）。なので：
\mathbf{A} =
\begin{pmatrix}
& e_1 & e_2 & e_3 \\
1 & 1 & 0 & 1 \\
2 & 1 & 1 & 0 \\
3 & 0 & 1 & 1
\end{pmatrix}
行列式を計算
第1行で展開すると：
\det \mathbf{A} = 1 \cdot \det\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} - 0 + 1 \cdot \det\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = 1 + 1 = 2
これ自体が $\mathbf{A}$ の「3×3 正方部分行列」（=$\mathbf{A}$ 自身）の行列式なので、$|\det| = 2 > 1$。よって TU の条件（任意の正方部分行列の行列式 $\in {0, \pm 1}$）を満たしません。
なぜ「奇閉路」だとダメなのか（直感）
有向グラフでは各辺の端点に $+1, -1$ という「符号」が付くので、サイクルを一周すると符号がキャンセルして $\det$ が 0 や $\pm 1$ に収まりやすい。
無向グラフだと両端点とも $+1$ なので「符号でキャンセル」ができません。ただし偶閉路だけなら頂点を「白黒」に塗り分けて符号を付与（=向きを付ける）ことができ、有向と同じ性質に戻せます。$K_3$ は**奇閉路（3-サイクル）**なので塗り分け不能 → TU 性が壊れる、というイメージです。
実際これは有名な定理になっていて、
無向グラフの接続行列が TU $\Leftrightarrow$ そのグラフが 2部グラフ（=奇閉路を持たない）
K₃ は奇閉路そのものなので、この定理からも TU ではないことが分かります。これが元記事の「2部グラフの接続行列は TU」とちょうど裏返しになっています。
まとめ
- 無向グラフの接続行列：頂点が辺の端点なら $1$、そうでなければ $0$
- $K_3$ の接続行列の行列式は $\pm 2$ なので TU の条件を満たさない
- 偶閉路は頂点を白黒に塗り分けて符号を付与（=向きを付ける）ことができ TU を保つが、奇閉路はそれができない
- 一般に「無向グラフの接続行列が TU $\Leftrightarrow$ そのグラフが 2部グラフ」が成り立つ