グラフ理論の問題

辺の本数と次数 横方向の辺は各行に $4$ 本ずつで $4\times 4=16$ 本、縦方向の辺は各列に $3$ 本ずつで $5\times 3=15$ 本あるので、$G$ の辺は $31$ 本である。

各頂点の次数は、角の $4$ 頂点が $2$、角以外の周上の頂点が $3$、内部の頂点が $4$ である。よって次数が奇数の頂点は角以外の周上の頂点で、
- 第 $1$ 行と第 $4$ 行：$(1,2),(1,3),(1,4)$ と $(4,2),(4,3),(4,4)$（各 $3$ 個）
- 第 $1$ 列と第 $5$ 列：$(2,1),(3,1)$ と $(2,5),(3,5)$（各 $2$ 個）

の合計 $10$ 個である。

問題の言い換え 長さ $L$ の閉じた歩道が辺 $e$ を $x_e(\ge 1)$ 回通るとき、各辺 $e$ を $x_e$ 本に増やした多重グラフでは、その歩道がオイラー閉路になるので、すべての頂点の次数が偶数である。したがって「余分に通った分」、すなわち各辺 $e$ を $x_e-1$ 本ずつ並べた多重グラフ $H$ では、次数が奇数になる頂点がちょうど $G$ の奇頂点 $10$ 個である。逆に、そのような $H$ を $G$ に付け加えた多重グラフは連結で全頂点の次数が偶数なので、オイラーの定理によりオイラー閉路をもち、それが長さ $31+|E(H)|$ の条件を満たす閉じた歩道になる。よって求める最小値は $31+\min |E(H)|$ である。

下界 $H$ の奇頂点は $10$ 個あり、$H$ の各連結成分の中で奇頂点は偶数個ずつあるので、$H$ の辺は奇頂点どうしを結ぶ $5$ 本の歩道（辺を共有しない）と残りに分けられる。したがって、$10$ 個の奇頂点を $5$ 組に分け、各組の 2 頂点間の距離を足した値を $D$ とすると $|E(H)|\ge D$ である。

距離が $1$ の組は隣り合う奇頂点の組である。奇頂点 $(1,2)$ の隣は $(1,1)$（次数 $2$）、$(1,3)$、$(2,2)$（次数 $4$）であるように、奇頂点どうしが隣り合うのは同じ辺（周の一辺）の上で隣り合う場合だけである。奇頂点は周の各辺ごとに $3,2,3,2$ 個の「一列に並んだかたまり」に分かれ、各かたまりの中で距離 $1$ の組は最大でも $1,1,1,1$ 組しか作れない。よって距離 $1$ の組は $4$ 組以下である。
- 距離 $1$ の組が $4$ 組のとき：第 $1$ 行と第 $4$ 行のかたまりから $1$ 個ずつ余り、それらが組になる。第 $1$ 行と第 $4$ 行の頂点の距離は $3$ 以上なので $D\ge 4\cdot 1+3=7$。
- 距離 $1$ の組が $3$ 組以下のとき：残りの $2$ 組以上は距離 $2$ 以上なので $D\ge 3\cdot 1+2\cdot 2=7$。

いずれにしても $|E(H)|\ge 7$ である。

$7$ を実現する例 次の $7$ 本の辺を 1 本ずつ $H$ とする。
$$(1,3)\text{-}(1,4),(4,3)\text{-}(4,4),(2,1)\text{-}(3,1),(2,5)\text{-}(3,5),$$
$$(1,2)\text{-}(2,2),(2,2)\text{-}(3,2),(3,2)\text{-}(4,2).$$
$H$ での次数は、$10$ 個の奇頂点がそれぞれ $1$、$(2,2),(3,2)$ が $2$、ほかは $0$ なので、$H$ の奇頂点はちょうど $G$ の奇頂点である。$G$ にこれを加えた多重グラフは連結で全頂点の次数が偶数だから、オイラー閉路をもつ。

よって最小値は $31+7=38$ である。

求めるのは中国人郵便配達問題（全辺を通る最短の閉歩道）の最小値である。

辺数: 横の辺は各行に 4 本で $4\times 4=16$、縦の辺は各列に 3 本で $5\times 3=15$、計 31 本。

次数: 角は 2、角以外の周上の頂点は 3、内部の頂点は 4。奇数次数の頂点は、上の行 $(1,2),(1,3),(1,4)$、下の行 $(4,2),(4,3),(4,4)$、左の列 $(2,1),(3,1)$、右の列 $(2,5),(3,5)$ の 10 個。

閉歩道の長さは $31+$（奇数次数頂点を 2 つずつ組にして結ぶ辺の重複の最小総長）である。これは奇数次数頂点の最小重み完全マッチング（格子上の距離）に等しい。

下界: 奇数次数頂点どうしで距離 1（隣接）の組になれるのは、上の行で 1 組（3 頂点が一列に並ぶので 2 頂点だけ）、下の行で 1 組、左の列で 1 組、右の列で 1 組の高々 4 組。
- 隣接組が 4 組のとき、残る上の行の 1 頂点と下の行の 1 頂点の距離は少なくとも 3（行が 3 つ離れている）なので、合計 $4+3=7$ 以上。
- 隣接組が 3 組以下のとき、残り 2 組は隣接しないので距離は各 2 以上（二部グラフで同じ色の頂点は偶数距離、異なる色でも隣接しなければ 3 以上）、合計 $3+2+2=7$ 以上。
- 隣接組が 2 組以下のとき、$2+2\times 3=8$ 以上。
よって最小は 7 以上。

上界: 組 $(1,2)$-$(1,3)$（距離 1）、$(4,2)$-$(4,3)$（1）、$(2,1)$-$(3,1)$（1）、$(1,4)$-$(2,5)$（2）、$(4,4)$-$(3,5)$（2）で総長 7。この 7 の辺を重複して加えると全頂点が偶数次数となり、連結なのでオイラー閉路が存在する。

したがって最小の長さは $31+7=38$。