前へ / 戻る

応用

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

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

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

デモ動画

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

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

今日のまとめ

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

宿題

• 授業時間に紙媒体で配布しますが、pdf もここから download できます。
• 提出方法：スキャンしたり写メを撮ったり、pdf を編集したりして、pdf ファイル・画像ファイル等を送信してください。
• 宛先は shiota＠is.kochi-u.ac.jp（＠は小文字）
• 件名は、組合せとグラフの理論第5回の宿題 [自分の学籍番号]
• 上手く送れない人はメールで連絡してください。
• 提出期限：5月26日(金) 10:30am

前へ / 戻る