組合せとグラフの理論(塩田)2024年度

授業形態ほか

  • 担当教員 : 理工学部 情報科学科 塩田研一
  • メールアドレスは shiota@is.kochi-u.ac.jp です。( @は小文字に直してください。)
  • 授業は対面で実施します。教室は 理工学部情報科学棟1階の共通講義室4 です。
  • 一昨年度のオンライン教材も一部修正の上掲載しておきますが、メインは対面授業です

教科書(必携)

  • R.J.ウィルソン著,西関隆夫・西関裕子訳,
    「グラフ理論入門 原書第4版」 ( 近代科学社 ),ISBN 4764902966
     (電子書籍の Kindle 版もあります。)
 教科書は必ず手に入れてください。

各回の教材

授業日講義内容(予定)
第1回4月12日グラフ理論の始まり、本講義の目標
第2回4月19日グラフの基本用語、同型、計算機上でのデータ表現
第3回4月26日グラフの名前と形容詞、グラフの演算、連結性
第4回5月10日道、連結度
第5回5月17日オイラー性、ハミルトン性
第6回5月24日木、全域木、幅優先探索・深さ優先探索
第7回5月31日閉路部分空間と電気回路への応用
第8回6月7日最短路問題、巡回セールスマン問題他
第9回6月14日平面性、オイラーの公式
第10回6月21日双対グラフ
第11回6月28日点彩色、平面グラフの面彩色
第12回7月5日ネットワークフロー
第13回7月12日最大フロー・最小カット定理、Menger の定理
第14回7月19日マッチング
第15回7月26日グラフ理論の最近の話題

宿題

  • 宿題はスキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等をメールに添付して提出してください。 pdf ファイルもこのページから download 出来ます。
  • メールアドレスは shiota@is.kochi-u.ac.jp です。( @は小文字に直してください。)
  • 上手く提出できない人は相談してください。
  • 宿題メールには数日のうちに添削して返信します。 指摘した個所が修正できたら再提出して頂いて構いません(それなりに加点します)。
  • 宿題を複数回分まとめて提出されると見落とす危険があります。 1回分ずつ送信してください。
  • 4月12日の宿題
  • 4月19日の宿題
  • 4月26日の宿題
  • 5月10日の宿題
  • 5月17日の宿題
  • 5月24日の宿題
  • 5月31日の宿題
  • 6月7日の宿題
  • 6月14日の宿題

e-ポートフォリオ

  • この授業は e-ポートフォリオ対象科目 です。
  • 宿題やプリント等を、適当なタイミングでアップロードしておいて頂ければ幸いです。

参 考

トップページ