2009年1月25日に実施した試験に関するコメント

おおむねこちらで想定していたくらいの点数分布でした(受験した人の間の平均点は71点). 点数に疑問のある人は気軽にメール下さい.

「強連結なn頂点のグラフで最も辺の数が少ないものはどんなグラフか」という 問題に対する解答の正当率が意外と低かったです.「強連結である」ということ は「有向グラフ」上で「任意の2点間に有向路がある」ということですから, どの2点u,vを選んでも「uからv」というパスだけでなく「vからu」というパスも 存在しなくてはなりません.また辺の数が最少ということなので,完全グラフと いった解答も不十分です.

解答を端的に言えば「n頂点から構成される有向な閉路」となります. ぐるぐる回ればどの2点間でも互いに到達できることはすぐにわかると思います. また辺がn-1本しかないと,グラフは木になってしまうので,どの2点間を結ぶ道 も1つしか存在せず,例えば u から v に行けるなら v から u には行けません. したがって「n 本の辺を使った閉路」が辺の数が最少であることがわかります.


Last modified: Fri Oct 12 09:02:38 JST 2007
by Ryuhei Uehara (uehara@jaist.ac.jp)
Valid HTML 4.0!