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

1. 頂点は半整数である。 $x$ を $P$ の頂点とし、$V_{+}=\{v\mid 0<x_v<\frac{1}{2}\}$, $V_{-}=\{v\mid \frac{1}{2}<x_v<1\}$ とおく。$d={\chi }_{V_{+}}-{\chi }_{V_{-}}$ として $x\pm \epsilon d$（$\epsilon >0$ は十分小）を考える。非負制約は $V_{+}\cup V_{-}$ 上で $x_v>0$ なので保たれる。辺 $\{u,v\}$ の制約がきつい（$x_u+x_v=1$）とき、$u,v$ のどちらかが $V_{+}$ ならもう一方は $V_{-}$ でなければならず（$x_u<\frac{1}{2}$ なら $x_v=1-x_u\in (\frac{1}{2},1)$）、このとき $d_u+d_v=0$ なので和は変わらない。両方が $\frac{1}{2}$ や $\{0,1\}$ の組なら $d_u=d_v=0$ である。きつくない制約は $\epsilon$ が小さければ保たれる。よって $x\pm \epsilon d\in P$ で、$x$ は頂点だから $d=0$、すなわち $x_v\in \{0,\frac{1}{2},1\}$ である（各頂点に辺があるので $x_v\le 1$）。

2. 頂点の特徴付け。 半整数の $x\in P$ について $V_0,V_{1/2},V_1$ を値 $0,\frac{1}{2},1$ の頂点の集合とする。$v\in V_1$ の隣接頂点はすべて $V_0$ に属し、$V_1$ と $V_{1/2}$ の間に辺はない。きつい制約は、$x_v=0$（$v\in V_0$）、$V_1$–$V_0$ 間の辺、$V_{1/2}$ 内部の辺である。
- $V_0$ の値は $x_v=0$ で決まる。$v\in V_1$ は隣接頂点 $u\in V_0$ をもつので $x_v+x_u=1$ から $x_v=1$ に決まる。
- $G[V_{1/2}]$ の連結成分 $C$ が奇サイクル $v_1{v}_2\cdots v_{2k+1}$ を含めば、$x_{v_i}+x_{v_{i+1}}=1$ を交代的に足し引きして $2x_{v_1}=1$ となり、連結性から $C$ 上の値はすべて一意に決まる。
- $C$ が二部グラフ（2 部 $A,B$）なら、$A$ 上で $+\epsilon$、$B$ 上で $-\epsilon$ ずらしても、$C$ 内の辺の和は不変で、$C$ から出る辺の相手は $V_0$（和は $\frac{1}{2}<1$）なので実行可能性は保たれる。よって頂点ではない。

したがって $x$ が頂点 $⟺$ $G[V_{1/2}]$ の各連結成分が奇サイクルを含む（$V_{1/2}=\varnothing$ なら $x$ は安定集合の特性ベクトル）。

3. 数え上げ。
(a) $V_{1/2}=\varnothing$：安定集合の個数。空集合、$\{0\}$、外周の $1$ 点集合 $5$ 個、外周の隣接しない $2$ 点集合 $5$ 個で、計 $12$ 個。

(b) $0\in V_{1/2}$：外周の頂点はすべて $0$ に隣接するので $V_1=\varnothing$ である。$S=V_{1/2}\cap \{1,\dots ,5\}$ とすると、$G[S\cup \{0\}]$ は中心 $0$ を通って連結である。これが奇サイクルを含む $⟺$ $S$ が外周の辺を含む（三角形 $0,u,v$ ができる。逆に $S$ が外周で安定なら星グラフで二部）。外周 $C_5$ の部分集合 $2^5=32$ 個のうち安定集合は $11$ 個なので、$32-11=21$ 個。

(c) $0\notin V_{1/2}\ne \varnothing$：$V_{1/2}\subseteq \{1,\dots ,5\}$ であり、$C_5$ の真部分集合が誘導する部分グラフはパスの和で二部グラフになる。よって $V_{1/2}=\{1,\dots ,5\}$ に限る。このとき $0$ は $V_{1/2}$ と隣接するので $x_0=0$ となり、$1$ 個。

合計は $12+21+1=34$ である。

$P$ は、辺制約のみの（分数）安定集合多面体である。この多面体の頂点は半整数的、すなわち $x\in \{0,\frac{1}{2},1{\}}^V$ であることが知られている。さらに、$x_v=\frac{1}{2}$ となる頂点の集合 $V_h$ について、誘導部分グラフ $G[V_h]$ の各連結成分が非二部グラフ（奇サイクルを含む）であることが、$x$ が頂点であるための必要十分条件である。$x_v=1$ の頂点の隣接点はすべて $0$ でなければならない。

これを使って $x_0$ の値で場合分けして数える。

1. $x_0=1$ のとき、外周はすべて $0$ となる。頂点は $1$ 個。
2. $x_0=\frac{1}{2}$ のとき、外周の各頂点は $0$ か $\frac{1}{2}$ である（$1$ は不可）。$\frac{1}{2}$ の外周頂点の集合を $S$ とする。$\{0\}\cup S$ は連結で、非二部であるためには $S$ が外周 $C_5$ の隣接する 2 頂点を含む必要がある（三角形ができる）。$C_5$ の安定集合（隣接頂点を含まない部分集合）は $1+5+5=11$ 個なので、$2^5-11=21$ 個。
3. $x_0=0$ のとき、外周 $C_5$ 上で考える。外周の真部分集合が誘導するのは道なので二部グラフであり、非二部になるのは外周全体が $\frac{1}{2}$ のときだけである。
- $V_h=\varnothing$ のとき、外周は $0/1$ 値で、$1$ の点が $C_5$ の安定集合をなす。空集合を含めて $11$ 個。
- $V_h$ が外周全体のとき、$1$ 個。
- 合計 $12$ 個。

以上より、頂点の個数は $1+21+12=34$。