組合せとグラフの理論（塩田）2025年度
授業形態ほか / 各回の教材 / 宿題

授業形態ほか

  • 担当教員 : 理工学部 情報科学科 塩田研一
  • メールアドレスは shiota＠is.kochi-u.ac.jp です。( ＠は小文字に直してください。)
  • 授業は対面で実施します。
  • ただし、第１回４月１８日は担当者が検査入院のため、 第２回４月２５日の授業も、担当者が忌引き休暇ため、非同期型オンライン教材での学習をお願いいたします。
  • 教室は 理工学部情報科学棟１階の共通講義室４です。

教科書（必携）

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

学期末レポート

  • 締め切りは 8月1日(金) 18:00 とします。
  • ここから download ( 全3ページ3問 ) ( 7月25日(金) 授業終了後 公開 )
  • 宿題と同様、pdf, 画像ファイル等の形で、 shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
  • 上手く送信できない人は相談してください。
  • 解答例

各回の予定とオンライン教材

  • 過去のオンライン教材も一部修正の上掲載してゆきますが、メインは対面授業です。
授業日講義内容(予定)
第1回4月18日グラフ理論の始まり、本講義の目標(非同期オンライン)
第2回4月25日グラフの基本用語、同型、計算機上でのデータ表現(非同期オンライン)
第3回5月2日グラフの名前と形容詞、グラフの演算、連結性
第4回5月9日道、連結度
第5回5月16日オイラー性、ハミルトン性
第6回5月23日木、全域木、幅優先探索・深さ優先探索
第7回5月30日閉路部分空間と電気回路への応用
第8回6月6日最短路問題、巡回セールスマン問題他
第9回6月13日平面性、オイラーの公式
第10回6月20日双対グラフ
第11回6月27日点彩色、平面グラフの面彩色
第12回7月4日ネットワークフロー
第13回7月11日最大フロー・最小カット定理、Menger の定理
第14回7月18日マッチング
第15回7月25日グラフ理論の最近の話題, 学期末レポート問題配布

配布物

宿題

e-ポートフォリオ

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

参　考

トップページ