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

0. 頂点の判定法. $x\in P$ に対し、頂点 $v$ がタイトとは ${\sum }_{e\in \delta (v)}{x}_e=1$ となることとする。$d\in {\mathbb{R}}^E$ が
$$d_e=0(x_e=0\text{ の辺}),\sum _{e\in \delta (v)}{d}_e=0(\text{タイトな頂点 }v)(\ast )$$
を満たせば、タイトでない制約には余裕があるので、十分小さい $\epsilon >0$ で $x\pm \epsilon d\in P$ となる。よって $x$ が $P$ の頂点であることは、$(\ast )$ を満たす $d$ が $d=0$ だけであること（タイトな制約の階数が $|E|$ であること）と同値である。

1. 頂点の特徴付け. $x$ を $P$ の頂点とし、$F=\{e\in E\mid 0<x_e<1\}$（分数辺）、$H=(V,F)$ とする。

(i) $x_e=1$ の辺 $e=uv$ について：$u$ の次数制約から $u$ に接続するほかの辺の値は $0$、$u$ はタイトである。$(\ast )$ を満たす $d$ は、$u$ でのタイトな等式でほかの辺の $d$ が $0$ なので $d_e=0$ となる。また値 $1$ の辺どうしは頂点を共有しない（マッチング $N$ をなす）。

(ii) タイトな頂点 $v$ が分数辺にちょうど $1$ 本だけ接続することはない。実際、その分数辺の値を $t\in (0,1)$ とすると、$v$ に接続するほかの辺の値は整数で和が $1-t\in (0,1)$ にならなければならず、不可能である。とくに、$H$ で次数 $1$ の頂点はタイトでない。

(iii) $H$ の辺を $1$ 本以上もつ連結成分 $K$ をとり、頂点集合を $U$、辺集合を $F_K$、$U$ のタイトな頂点の集合を $T$ とする。$d$ を $F_K$ 上だけで $0$ でないベクトルとすると、$F_K$ の辺は $U$ の頂点にしか接続せず、$U$ のタイトな頂点 $v$ に接続する値が正の辺はすべて $F_K$ に含まれる（(i) より値 $1$ の辺は分数辺と端点を共有しない）。したがって $(\ast )$ は、$T$ の各頂点 $v$ について ${\sum }_{e\in F_K\cap \delta (v)}{d}_e=0$ という $|T|$ 本の一次方程式（未知数 $|F_K|$ 個）になる。$x$ が頂点なのでこの連立方程式の解は $0$ だけであり、とくに $|F_K|\le |T|\le |U|$ が必要である。一方 $K$ は連結なので $|F_K|\ge |U|-1$。

• $|F_K|=|U|-1$（$K$ が木）のとき：$|T|\ge |U|-1$ が必要。しかし辺をもつ木には葉が $2$ 個以上あり、(ii) より葉はタイトでないので $|T|\le |U|-2$。矛盾。
• $|F_K|=|U|$ のとき：$|T|=|U|$、すなわち $U$ のすべての頂点がタイトである。(ii) より $K$ に葉はなく、すべての次数が $2$ 以上で辺数と頂点数が等しい連結グラフなので、$K$ はサイクルである。偶サイクルなら辺に交互に $+1,-1$ を置いた $d$ が $(\ast )$ を満たすので不適。奇サイクルなら、サイクルの接続行列（$|U|\times |U|$）の行列式は $\pm 2\ne 0$ で、解は $0$ だけになる。このとき各頂点で隣り合う $2$ 辺の値の和が $1$ なので、辺の値を順に $a_1,a_2,\dots ,a_{2m+1}$ とすると $a_1+a_2=a_2+a_3=\cdots =a_{2m+1}+a_1=1$ から $a_1=a_3=\cdots =a_{2m+1}=a_2=\cdots$ となり、すべて $\frac{1}{2}$ である。
• $|F_K|>|U|$ のとき：未知数の個数が方程式の本数より多いので $0$ でない解があり、不適。

以上より、$P$ の頂点 $x$ は次の形をしている：値 $\frac{1}{2}$ の辺が頂点を共有しない奇サイクル $C_1,\dots ,C_k$ をなし、値 $1$ の辺がマッチング $N$ をなし、$N$ と各 $C_j$ は頂点を共有せず（$C_j$ の頂点はサイクルの $2$ 辺でタイト）、ほかの辺の値は $0$。

逆に、このようなベクトル $x$ は明らかに $P$ に属し、頂点である。実際 $(\ast )$ を満たす $d$ は、値 $0$ の辺で $0$、$N$ の辺で (i) と同じ理由で $0$、各 $C_j$ の辺では $C_j$ の頂点でのタイトな等式（ほかの辺の $d$ は $0$）が奇サイクルの接続行列の連立方程式になるので $0$ である。

2. 数え上げ. 整数でない頂点は $k\ge 1$ のものである。$K_5$ の頂点は $5$ 個で、長さ $3$ 以上の奇サイクルを $2$ 個、頂点を共有せずにとるには $6$ 頂点以上が要るので $k=1$ であり、サイクルの長さは $3$ か $5$ である。

• 長さ $5$ のサイクル（ハミルトン閉路）：$\frac{(5-1)!}{2}=12$ 個。残りの頂点はないので $N=\varnothing$。$12$ 個。
• 長さ $3$ のサイクル（三角形）：$\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 個。残りの $2$ 頂点を結ぶ $1$ 本の辺を $N$ に入れるか入れないかで $2$ 通り。$10\times 2=20$ 個。

よって整数でない頂点の個数は $12+20=32$。

（参考：整数の頂点はマッチング全体で $1+10+15=26$ 個あり、$P$ の頂点は全部で $58$ 個である。）

$P$ は分数マッチング多面体である。その頂点は次のように特徴づけられる（バリンスキーの定理）: 頂点 $x$ は半整数的で、$x_e=1$ となる辺は互いに素な辺（マッチング）をなし、$x_e=\frac{1}{2}$ となる辺は、互いに素な奇サイクルの和集合で、これらはマッチング辺と頂点を共有しない。逆に、そのような形のベクトルはすべて頂点である（サポートの各連結成分が辺または奇サイクルで、基本解になっている）。

整数でない頂点は、奇サイクルを少なくとも 1 つ含むもの。$K_5$ では 5 頂点なので、奇サイクルは三角形（3 頂点）か 5 サイクルのみで、奇サイクルを 2 つ含むことはできない（3+3>5）。

(1) 三角形を 1 つ含む場合: 三角形の選び方は $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通り。残り 2 頂点は、(a) その 2 頂点を結ぶ辺に $x=1$ を置く、(b) 何も置かない（0）の 2 通り。いずれも頂点である（(b) でも、三角形の頂点 3 本の等式と他の 7 辺の $x_e=0$ で 10 個の一次独立な有効制約が得られる）。よって $10\times 2=20$ 個。

(2) 5 サイクル（ハミルトン閉路）に $\frac{1}{2}$ を置く場合: 閉路の個数は $\frac{(5-1)!}{2}=12$ 個。5 頂点の制約すべてが等号で、5 サイクルの辺の係数行列は正則（奇サイクル）なので頂点。

合計 $20+12=32$。

検算: 分数頂点で 5 頂点を使うので、マッチング辺と三角形の組合せの上限を確かめると、三角形 + マッチング辺は、三角形 10 通り × 残りの辺 1 通りで 10、三角形のみは 10、合わせて 20。5 サイクル 12。計 32。