京都大学 2008年 文系 第5問（甲） 解説

方針・初手

正 $n$ 角形の頂点をノード、辺と弧をエッジとするグラフの一筆書き（オイラー閉路）の数を求める問題です。各頂点には線分2本と弧2本の計4本のエッジが接続しているため、一筆書きが可能です。

経路の全体像を捉えるため、各頂点間の移動を「右回り」と「左回り」に分類し、入る回数と出る回数が等しくなるという条件から、経路のパターンを3つのケースに絞り込みます。後半の $b$ の計算では、直接数えるのではなく、「始点を指定しない一筆書き（巡回経路）」の総数と $a, b$ の関係性を利用して求めます。

解法1

正 $n$ 角形の頂点を時計回りに $V_1, V_2, \ldots, V_n$ とし、$A = V_1$ とする（$V_{n+1} = V_1$ と考える）。

隣り合う頂点 $V_i, V_{i+1}$ を結ぶエッジは、正 $n$ 角形の辺と外接円の弧の2本がある。これを「ブロック $i$」と呼ぶ。

一筆書きの経路上で、ブロック $i$ のエッジを $V_i \to V_{i+1}$ の向き（右回り）に通る回数を $R_i$、$V_{i+1} \to V_i$ の向き（左回り）に通る回数を $L_i$ とする。各ブロックにはエッジが2本あるため、常に $R_i + L_i = 2$ である。

一筆書きの経路では、すべての頂点において「入るエッジの数」と「出るエッジの数」が等しくならなければならない。頂点 $V_i$ に入るエッジの数は $R_{i-1} + L_i$、出るエッジの数は $L_{i-1} + R_i$ であるため、

$$ R_{i-1} + L_i = L_{i-1} + R_i \iff R_i - L_i = R_{i-1} - L_{i-1} $$

すなわち、$R_i - L_i$ はすべてのブロックで一定の値 $d$ をとる。

$R_i + L_i = 2$ より $d$ は偶数であり、取りうる値は $d = 2, -2, 0$ の3通りである。

(i) $d = 2$ のとき（全体を右回りに2周する経路）

すべてのブロックで $R_i = 2, L_i = 0$ となる。各ブロックで「1周目に線分、2周目に弧」か「1周目に弧、2周目に線分」かの2通りの選び方がある。ブロックは $n$ 個あるため、経路の数は $2^n$ 通りである。

(ii) $d = -2$ のとき（全体を左回りに2周する経路）

(i) と同様の対称性から、経路の数は $2^n$ 通りである。

(iii) $d = 0$ のとき（各ブロックで右回りと左回りを1回ずつ通る経路）

すべてのブロックで $R_i = 1, L_i = 1$ となる。まず、各ブロックの2本の辺のうち、どちらを右回りに、どちらを左回りに通るかを決める。各ブロックにつき2通りあるため、全体で $2^n$ 通りの「有向グラフ」ができる。

このうちの1つの有向グラフを固定して、頂点 $A$ を始点とする経路の数を考える。ある境界 $m$（$1 \leqq m \leqq n$）が存在して、

• $2 \leqq k \leqq m$ の頂点は左方向（$V_1$ 側）に出る
• $m+1 \leqq k \leqq n$ の頂点は右方向（$V_1$ 側）に出る

という構成でなければ、途中でサイクルができて一筆書きが成立しない。境界 $m$ の選び方は $n$ 通りある。

また、$A$ からの「最初の一歩」は右と左の2通り選べる。

したがって、1つの有向グラフに対して経路は $n \times 2 = 2n$ 通りある。有向グラフは $2^n$ 通りあるため、このケースの経路の総数は $2n \times 2^n = n \cdot 2^{n+1}$ 通りである。

$a$ の算出

以上より、始点 $A$ からの一筆書きの総数 $a$ は、

$$ a = 2^n + 2^n + n \cdot 2^{n+1} = 2 \cdot 2^n + n \cdot 2^{n+1} = 2^{n+1} + n \cdot 2^{n+1} = (n+1)2^{n+1} $$

$b$ の算出

図形 $F$ における「始点・終点を区別しない一筆書きの巡回経路（オイラー回路）」の総数を $N$ とおく。

各オイラー回路は頂点 $A$ を2回通過するため、$A$ から出発するタイミングは2回ある。よって $a = 2N$ である。

一方、辺の中点 $B$ は一筆書きの途中で1回しか通過しないため、巡回経路を $B$ で切り開いて始点とするタイミングは1回しかない。よって $b = N$ である。

したがって、$b = \dfrac{a}{2}$ が成り立つため、

$$ b = \frac{(n+1)2^{n+1}}{2} = (n+1)2^n $$

解説

グラフ理論の「オイラー閉路」をテーマにした難問です。有向グラフにおけるオイラー閉路の数を求める「BEST定理（行列木定理）」の背景知識があると、(iii) で「最後に退出する辺が有向木を作る」という発想に至りやすくなります。

また、$b$ を直接数え上げるのは至難の業ですが、「オイラー回路全体」と「各頂点からの出発方法」の対応関係に気づけば、$b = a/2$ という関係から一瞬で答えを導くことができます。

答え

$$ a = (n+1)2^{n+1} $$

$$ b = (n+1)2^n $$