組合せとグラフの理論（塩田）2021年度
授業形態ほか / 学期末レポート / 各回の教材 / 宿題

授業形態ほか

  • 担当教員 : 理工学部 情報科学科 塩田研一
  • このクラスは html で教材を提示して非同期で行います。
  • 宿題提出・質問はメールで受け付けます。
  • メールアドレス : shiota＠is.kochi-u.ac.jp ( ＠は小文字に直してください。)
    • ＠の後ろは is.kochi-u.ac.jp です。皆さんの s.kochi-u.ac.jp より1文字多いのでお間違え無いように。
  • 宿題を提出して頂いたメールには確認メールを返信するようにしています。数日しても返信が無い場合はお問い合わせください。 指摘した個所が修正できたら再提出して頂いて構いません。
  • 宿題を複数回分まとめて提出されると見落とす危険があります。 多少面倒でも１回分ずつ送信してください。

教科書（必携）

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

学期末レポート

  • 対面試験に代えて学期末レポートを課します。
  • 締め切りは 8月6日(金) 12:00 とします。
  • ここから download（全5ページ5問）...【1】(6) の行列を訂正しました。(7月28日15:15)
  • 宿題と同様、pdf, 画像ファイル等の形で、 shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
  • 上手く送信できない人は相談してください。

各回の教材

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

配布物

宿題

e-ポートフォリオ

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

参　考

トップページ