高知大学大学院理学研究科情報科学専攻（専門）

13 G = (V, E) を有限単純グラフとする。 ( V は G の頂点集合を、 E は G の辺集合を表す。 ) e ∈ E のふたつの端点を v, w ∈ V とするとき e = vw と表示することにする。また G において次のような辺の列を「閉じた小径」という :

\begin{matrix}e_{1} = v_{1}v_{2}, e_{2} = v_{2}v_{3}, ⋯, e_{i} = v_{i}v_{i+1}, ⋯, e_{m} = v_{m}v_{1} \\ ( ただし e_{1}, e_{2}, ⋯, e_{m} は全て異なる ) \end{matrix}

閉じた小径の含む辺の本数を、その小径の「長さ」と定める。

問 n を 3 以上の自然数とするとき、頂点数 n の完全グラフ K_{n} に含まれる最長の閉じた小径の長さを求めよ。

[figure]
完全グラフ K_{6} \begin{matrix}K_{6} に含まれる閉じた小径の例 \\ ( 長さ 11、最長ではない ) \end{matrix}

13 専門受験番号