前へ / 戻る

応用

　余裕のある諸君は こちらのプリント もご覧ください。

1. 完全グラフのオイラーサイクル
2. 順列の半ハミルトン道
3. ドゥブリュエイン列

について書いてあります。

デモ動画

　mp4 が再生可能なブラウザでご覧ください。

• オイラーグラフ
  • $K_7$( 365KB )
  • $K_{4,6}$( 395KB )
  • 正八面体グラフ( 309KB )
  • 4次元立方体グラフ( 347KB )
• オイラーでない半オイラーグラフ
  • $K_{2,5}$( 317KB )
  • ランダム( 296KB )

今日のまとめ

• オイラーグラフ・半オイラーグラフを定義し、一筆描きの定理を構成的に証明しました。
• もうひとつの一筆描きアルゴリズムとしてフルーリーのアルゴリズムを紹介しました。
• ハミルトングラフを定義しましたが、大きなグラフでは判定が難しいという話をしました。
• 有向グラフでもオイラー性を考えました。

宿題

• ここから download してください。
• 提出期限：5月27日(金)
• 提出方法：スキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等を shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
  • 上手く送れない人はメールで連絡してください。
• 件名に「組合せとグラフの理論第5回の宿題」と書いておいて頂けると有難いです。
• 宿題を複数回分まとめて提出されると見落とす危険があります。１回分ずつ送信してください。

前へ / 戻る