12 _{専門}_{受験番号}

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

12 次の A , B のうち、いずれか一つを選んで解答せよ。

A F = GF(2) を 2 元体とし、 g(x) = x^{3} + x^{2} + 1 を生成多項式とする F 上の符号長 7 の巡回符号を C とする。 ( すなわち C は、 g(x) によって生成される F [x]/(x^{7} − 1) のイデアルと同一視される符号である。 ) このとき、 C の生成行列 G、パリティ検査行列 H、情報次元 k、最小距離 d をそれぞれ答えよ。 ( 計算過程も述べること。 )

B グラフ理論に関する次の問いに答えよ。ただし、ここでは有限単純無向グラフを単にグラフと言い、グラフ G の補グラフを\overline{G} で表す。また、グラフ G の頂点に k色の色を割り当てて隣接するどの 2 頂点も異なる色が割り当てられるようにできるとき、 G は k-彩色可能であると言う。

(1) 頂点数 9 のグラフ G で、 G と\overline{G} が共に 3-彩色可能であるような例を挙げよ。

(2) 頂点数 10 以上のグラフ G については、 G と\overline{G} の少なくとも一方は 3-彩色不可能であることを示せ。