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

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

A. 古典的暗号系と公開鍵暗号系の相違点を、その設計方法・安全性等の観点から比較して論ぜよ。

B. グラフ理論に関する次の問いに答えよ。ただし、以下有限単純無向グラフを単にグラフと言い、また、連結グラフ G に対して、頂点集合が G と一致するような部分グラフ H で、かつ木であるものを「G の全域木」と言う。

(1) G が頂点数 p の連結グラフで、辺数 p − 1 の任意の G の部分グラフが G の全域木であるならば、 G は木であるかまたはサイクルであることを示せ。

(2) 任意のふたつの全域木が同型となるような連結グラフで、木でもサイクルでもない例をひとつ挙げよ。

13 専門受験番号