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)