凸最適化・組合せ最適化の問題

頂点の特徴づけ $P$ は有界である（各頂点 $v$ はある辺に含まれるので $0\le x_v\le 1$）。$x\in P$ が頂点であることは、$x$ で等号の成り立つ制約（有効制約）の係数ベクトルが階数 $6$ をもつことと同値である。

よく知られているように（Balinski の定理）、$P$ の頂点はすべて半整数、すなわち $x\in \{0,\frac{1}{2},1{\}}^V$ である。そこで $V_0,V_{1/2},V_1$ をそれぞれ値が $0,\frac{1}{2},1$ の頂点の集合とする。実行可能性から、$V_1$ の頂点の隣接点はすべて $V_0$ に属する（$1+\frac{1}{2}>1$, $1+1>1$）。

有効制約を調べる。
- $v\in V_0$ では $x_v=0$ が有効で、$x_v$ は決まる。
- $v\in V_1$ では隣接点 $u\in V_0$ との辺の制約 $x_u+x_v=1$ が有効（$G$ に孤立点はない）で、$x_u=0$ と合わせて $x_v$ は決まる。
- $V_{1/2}$ の頂点については、有効制約は $V_{1/2}$ 内部の辺 $x_u+x_v=1$ だけ（$\frac{1}{2}+0<1$ なので $V_0$ との辺は有効でない）。誘導部分グラフ $G[V_{1/2}]$ の連結成分 $K$ ごとに、方程式系 $x_u+x_v=1(\{u,v\}\in E(K))$ の解が一意であることが必要十分である。$K$ が 2 部グラフなら、2 部の一方に $+\epsilon$、他方に $-\epsilon$ を加えても有効制約は保たれるので一意でない。$K$ が奇閉路を含めば、奇閉路上で $x_v=\frac{1}{2}$ が決まり、連結性から全体が決まる。

したがって、$x\in \{0,\frac{1}{2},1{\}}^V$ が頂点 $⟺$ $x\in P$ かつ $G[V_{1/2}]$ のどの連結成分も奇閉路を含む。

(i) $V_{1/2}=\varnothing$（整数の頂点） $G$ の安定集合の個数に等しい。三角形 $\{1,2,3\}$ から高々 1 点（4 通り）、$\{4,5,6\}$ から高々 1 点（4 通り）を選び、$3$ と $4$ を同時に選ぶ 1 通りを除いて $4\cdot 4-1=15$ 個。

(ii) $V_{1/2}\ne \varnothing$ $G$ の奇閉路は 2 つの三角形だけなので、$V_{1/2}$ の各連結成分はどちらかの三角形を含む。条件を満たす $V_{1/2}$ と、残りの頂点への $0,1$ の割り当て（$V_{1/2}$ に隣接する頂点は $0$、$V_1$ は安定集合）を数える。
- $V_{1/2}=\{1,2,3\}$: 頂点 $4$ は $3$ に隣接するので $x_4=0$。$x_5,x_6$ は $(0,0),(1,0),(0,1)$ の 3 通り。
- $V_{1/2}=\{1,2,3,4\}$: $5,6$ は $4$ に隣接するので $0$。1 通り。
- $V_{1/2}=\{1,2,3,4,5\}$, $\{1,2,3,4,6\}$: 残りの 1 点は $0$。各 1 通りで計 2 通り。
- 対称に、$\{4,5,6\}$ で 3 通り、$\{3,4,5,6\}$ で 1 通り、$\{1,3,4,5,6\}$, $\{2,3,4,5,6\}$ で 2 通り。
- $V_{1/2}=V$: 1 通り。

一方 $\{1,2,3,5\}$ や $\{1,2,3,5,6\}$ などは、$\{5\}$ や $\{5,6\}$ という 2 部グラフの成分を含むので頂点にならない。よって (ii) の個数は
$$(3+1+2)+(3+1+2)+1=13.$$

以上より、頂点の個数は $15+13=28$。

辺による安定集合多面体の LP 緩和 $P$（辺制約のみ）の頂点は半整数的であること（Balinski, Nemhauser-Trotter）を用いる。頂点 $x$ について $O=\{v:x_v=1\}$, $H=\{v:x_v=1/2\}$, $Z=\{v:x_v=0\}$ とおく。

頂点であるための条件を、有効な（等号で成り立つ）制約の階数が 6 になる条件として整理する。
- 実行可能性より、$O$ は独立集合で、$O$ の隣接点はすべて $Z$ に入る（$O$ と $H$ の間に辺があると $1+1/2>1$）。
- 等号で成り立つ制約は、$x_v=0$（$v\in Z$）、$O$-$Z$ を結ぶ辺、$H$ 内の辺である。$O$ の各頂点には隣接点があるので（このグラフに孤立点はない）、$O$ の成分は $Z$ の隣接点から決まる。
- $H$ の成分が一意に決まるための必要十分条件は、$G[H]$ の各連結成分が奇数長の閉路を含む（非二部）ことである（二部成分があれば $+t,-t$ の自由度が残る）。

したがって頂点は、組 $(H,O)$ で、(i) $G[H]$ の各連結成分が非二部、(ii) $O$ は独立集合で $H\cup N(H)$ と交わらない、を満たすものと 1 対 1 に対応する（残りは $Z$）。

このグラフの奇数閉路は三角形 $\{1,2,3\}$, $\{4,5,6\}$ のみ（3 と 4 を結ぶ辺は橋）。各成分が非二部となる $H$ を列挙すると次の 10 通り。
(1) $\varnothing$、(2) $\{1,2,3\}$、(3) $\{1,2,3,4\}$、(4) $\{1,2,3,4,5\}$、(5) $\{1,2,3,4,6\}$、(6) $\{1,\dots ,6\}$、(7) $\{4,5,6\}$、(8) $\{3,4,5,6\}$、(9) $\{1,3,4,5,6\}$、(10) $\{2,3,4,5,6\}$。
（例えば $\{1,2,3,5\}$ は成分 $\{5\}$ が二部なので不可。三角形が 3,4 を含むので、両方の三角形を含めば 3-4 の辺で連結になる。）

各 $H$ について、$C=V\setminus (H\cup N(H))$ の誘導部分グラフの独立集合（空集合を含む）の個数を数える。
(1) $H=\varnothing$：$G$ の独立集合の個数。三角形ごとに独立集合は $\varnothing$ と 1 点で 4 通り、$3$ と $4$ を同時に選べないので $4\times 4-1=15$。
(2) $C=\{5,6\}$（辺 56）：3。(7) $C=\{1,2\}$：3。
(3)(4)(5)(6)(8)(9)(10)：$C=\varnothing$ なので各 1。

合計：$15+3+3+7\times 1=28$。

検算：整数頂点（安定集合）が 15 個、半整数の頂点が $28-15=13$ 個。(1) 以外の $H\ne \varnothing$ の分は $3+1+1+1+1+3+1+1+1=13$ で一致。