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

次の \fbox{{\bf A}} , \fbox{{\bf B}} のうち、
いずれか一つを選んで解答せよ。
\vspace{3em}
%
\begin{description}
%
\item[\fbox{{\large\bf A}}\quad]
$F=\mbox{GF}(2)$ を 2元体とし、
$g(x)=x^3+x^2+1$ を生成多項式とする $F$ 上の
符号長 7 の巡回符号を $C$ とする。
( すなわち $C$ は、$g(x)$ によって生成される $F[x]/(x^7-1)$ 
のイデアルと同一視される符号である。)\\
\hspace*{5pt}
このとき、$C$ の生成行列 $G$、パリティ検査行列 $H$、情報次元 $k$、
最小距離 $d$ をそれぞれ答えよ。
( 計算過程も述べること。)
%
\vfill
%
\item[\fbox{{\large\bf B}}\quad]
グラフ理論に関する次の問いに答えよ。
ただし、ここでは有限単純無向グラフを単にグラフと言い、
グラフ $G$ の補グラフを $\overline{G}$ で表す。
また、グラフ $G$ の頂点に $k$色の色を割り当てて
隣接するどの2頂点も異なる色が割り当てられるようにできるとき、
$G$ は $k$-彩色可能であると言う。
%
\begin{itemize}
\item[(1)]
頂点数 9 のグラフ $G$ で、
$G$ と $\overline{G}$ が共に 3-彩色可能であるような例を挙げよ。
\vspace{3pt}
\item[(2)]
頂点数 10 以上のグラフ $G$ については、
$G$ と $\overline{G}$ の少なくとも一方は 3-彩色不可能であることを示せ。
\end{itemize}
\end{description}
\vfill
\end{document}