グラフ理論試験問題とコメント

• 試験問題(2002年7月25日実施) PS, PDF
• 第1問はレポート課題を少々変えて出題. 第2問と第3問はノートに 書いてあることが理解できていれば(あるいは丸暗記していれば)解答できる問題. かなり易しくしたつもりであったが, 思ったよりも正解率が低かった. とくに, 第2問の証明ができていた人が一人もいなかったのが残念である. 第3問は多くの人ができていた. 第2問と第3問はノートを見れば答えは分かるので, ここでは解説を省略する(第3問の(b)の例は挙げておく).
• 第1問はさまざまな解答があり, おもしろかった. 得点の対象になる 解答の概略を示しておこう. 以下, 各節点vにつける番号をl(v)で表す (つまり関数 l: V → {1, 2, ..., n} (nは節点数|V|)).
  • 深さ優先探索を利用する方法. はじめに k := n とする. 深さ優先探索の際, ある節点vから出ている全ての枝が探索済になった時点で l(v) := k とし, さらに k := k - 1 とする. 深さ優先探索が終了したのち, 未探索の節点が残っていれば, そのような節点からさらに同様に深さ優先探索を行う. これを未探索の節点がなくなるまで行う. (連結無向グラフと異なり, ある節点から他の任意の節点への有向路があるとは 限らないので, 後半の操作が必要になる.) このアルゴリズムがO(m+n)時間で動作するのは明らか. 正当性は, ある節点vに番号l(v)がつく時点では, vから有向パスをたどって 到達できる全ての節点にl(v)よりも大きな番号がすでについていることが 深さ優先探索の性質よりいえることから従う. 無駄がないことから実用上最も高速で, 最もスマートな解答と思う. 残念ながらこの解答は二人しかいなかった.
  • 入次数indeg(v)を利用する方法. はじめに k := 1 とする. indeg(v) = 0 の節点vを一つ見つけて l(v) := k としたのち k := k + 1 とし, 節点vとvに接続する枝をグラフから消去する操作を, 全ての節点に番号がつくまで反復する. 基本的なアルゴリズムは以上であるが, O(m + n)時間で動作するためには 多少工夫がいる. indeg(v) = 0 の節点vを一つ取り出す操作をO(1)時間でできるよう, そのような節点の集合をキューやスタックなどに蓄えておく点と, vをグラフから消去する際, vから出る各枝(v, w)に対して indeg(w) := indeg(w) - 1 と更新する点くらいは 書いて欲しかったが, このような記述なく線形時間と主張している 解答が多かった(大きな減点はしていないのでご安心を). これは一番自然で, 普通に考えるとまず思いつく方法と思う. 実際, この解答は比較的多かった.
  • 枝の両端点の番号の大小が条件をみたしていない場合に番号を入れ替える 操作を反復する方法. 枝を調べる順序に自由度があり, それによって 最悪計算時間も変わってくるが, 私が考えるかぎり, この方法ではせいぜいO(nm)時間の アルゴリズムしか作れないので, 多少減点している.
    • 計算時間を解析しやすいのは k := 1, 2, ..., n の順に以下を反復する方法. l(v) = kをみたす節点vに対し, l(u) > k となる枝 (u, v) が存在すれば u と v の番号を入れ替える(入れ替えの後は l(u) = k となるので, 今度は節点uについて同様のチェックを行う)操作を, そのような枝が存在するかぎり 反復し, そのような枝がなくなった時点で次のkに進む. このアルゴリズムでは番号kが可能な限り前に押されていく感じの動作に なるが, ある一つの番号kに対して入れ替えが起り得る枝として チェックする枝の本数はたかだかmである. (番号kに対して走査した節点に入ってくる枝の合計. グラフが非巡回的なので, 一つの節点は一度しか操作しないのでOK.) よって, この順序で枝を調べると, O(mn)時間で抑えられる.
    • じつは, 条件をみたさない任意の枝を一つ見つけて両端点の番号を 入れ替える方法でも, 入れ替えの回数がO(n²)であることが 証明できるが, 証明はそれほど簡単ではない. (推移閉包をとったグラフを考えて, そのグラフ上で条件を満たしていない 枝の本数を考えると, それが単調に減ることがいえる.) なお, 番号の入れ替えのたびに, 新たに条件をみたさなくなった枝を 見つけないといけないので, 1回の入れ替えあたり節点の最大次数（≦n）の 計算時間が必要. よって, 単純に評価すると計算時間はO(n³).
    このタイプの解答は非常に多かった. ただし, 計算時間をきちんと 評価していた解答はほとんどなかった. とくに, 上の二つ目のタイプの 枝の探索順序を指定しない場合, 有限時間で止まるかどうかも本当は 自明ではない. ただ, 証明は易しくないので, あまり大きな減点はしなかった.
  • 各節点を始点とする最長路の長さをまず計算し, その大小関係に 矛盾しないように番号をつける方法. 最長路を求める問題は, 一般のグラフではじつはNP困難であるが, 非巡回グラフでは線形時間で求められる. (非巡回グラフの最長路は, クリティカルパスと呼ばれ, スケジューリング などでは重要な概念である. クリティカルパスは通常グラフ全体の中での 最長路を指すが, この計算過程で各節点から出ていく路の中で最長のもの も計算できる.) 正しく番号づけはできるし, 上記の理由で線形時間で動作するので, 一見満点に見えるが, 最長路長の計算をする線形時間のアルゴリズムは ほぼそのまま番号づけのアルゴリズムに変形できるので (最長路長計算のアルゴリズムは第1問の番号づけを利用して動作するすると いってもいい), アルゴリズムを構築するという観点からはセンスがない. また, アルゴリズムが線形時間で動作することがきちんと言えている人は 一人もいなかった. よって若干の減点としている.
  正しく動作する方法は, 大きく分けてだいたい以上の4通りである. そのほか, 幅優先探索に基づく方法を書いていた人も若干いたが, これは正しく動作しないので, おまけの加点をする程度になっている.
• 第3問(b)の解答例. 以下のように3点の例が作れる. できるだけ ややこしい例が出てこないようにと思って, 5節点以下という条件をつけたら, 意味のない節点を無理やり追加してわざわざ5節点にしている人が 多くいたのが少々笑えた.
  

柳浦のホームページ