\documentstyle[12pt,a4j]{jarticle}
\pagestyle{empty}
\begin{document}
\begin{center}
{\bf 高知大学大学院 理学研究科 情報科学専攻 入学試験問題}
\vspace{1em}\\
{\bf 平成9年度1次募集 専門選択問題 13}
\vspace{2em}
\end{center}

グラフ理論に関する次の問題 \fbox{{\bf A}} , \fbox{{\bf B}} のいずれか１問を選択し解答せよ。
ただし以下、有限単純無向グラフを単にグラフと言う。
\vspace{3em}

\hspace*{-25pt}\fbox{{\bf A}}\quad
図のように $g$ 個の穴をもつ閉じた曲面（に同相な図形）を種数 $g$ の曲面という。
グラフ $G$ が、
種数 $g$ の曲面上に辺を交差させることなく描くことはできるが、
種数 $g-1$ の曲面上には辺を交差させることなく描くことはできないとき、
$G$ の種数は $g$ であるという。

頂点数6の完全グラフ $K_6$ の種数を求めよ。
（理由も述べよ。）

（図省略)

\vfill
\hspace*{-25pt}\fbox{{\bf B}}\quad
グラフ $G$ から、その線グラフ $L(G)$ を次のように定める : 
$L(G)$ の頂点集合は $G$ の辺集合 $E$ であり、
$e,f\in E$ が $G$ で隣接するときに
$L(G)$ の頂点として $e$ と $f$ は $L(G)$ で隣接することとする。

連結グラフ $G$ の全ての辺を丁度一度ずつ通る閉じた小道が存在するとき、
$G$ をオイラー・グラフという。
また、連結グラフ $G$ の全ての頂点を丁度一度ずつ通る閉路が存在するとき、
$G$ をハミルトン・グラフという。

以上の定義のもと、次の問に答えよ。
\begin{itemize}
\addtolength{\itemsep}{-8pt}
\item[(1)]
オイラー・グラフの線グラフはオイラー・グラフであることを示せ。
\item[(2)]
オイラー・グラフの線グラフはハミルトン・グラフであることを示せ。
\item[(3)]
ハミルトン・グラフの線グラフはハミルトン・グラフであることを示せ。
\end{itemize}
\vfill

\end{document}