グラフとネットワーク

なし

グラフやネットワークの関する基本的な概念とそれらに関する性質、代表的な問題のアルゴリズムについて概説する。
グラフやネットワークに関する基本的概念を理解し、様々な問題をグラフを用いて表現できること、グラフやネットワークに関する簡単な証明を行うことができるようになることを目標とする。

離散数学、プログラミング通論、アルゴリズム論第一

オペレーションズ・リサーチ基礎

参考書:
R.J. ウィルソン (著), 西関隆夫, 西関裕子 (訳), 「グラフ理論入門 原書第4版」, 近代科学社
惠羅博,土屋守正,「増補改訂版 グラフ理論」, 産業図書
藤重悟,「グラフ・ネットワーク・組合せ論」, 共立出版
繁野麻衣子, 「ネットワーク最適化とアルゴリズム」, 朝倉書店
他

(a)授業内容
第1回 グラフの基本概念
第2回 種々のグラフ、次数
第3回 道と閉路
第4回 周遊性
第5回 木
第6回 平面グラフ
第7回 中間試験と解説
第8回 連結性
第9回 グラフの彩色
第10回 彩色と独立集合
第11回 マッチング
第12回 辺彩色とマッチング
第13回 最大流とカット
第14回 最大流、様々なグラフ族
第15回 期末試験と解説

(b)授業の進め方
講義形式で行う。講義内容に合わせて演習問題も解かせる。

予習、復習を行い、課題を与えた場合はそれに取り組むこと。

評価方法:中間試験、期末試験の成績に基づいて評価を行う。
評価基準:達成目標に記した内容を一定の水準以上満たすことを合格の基準とする。

なるべく講義終了後に講義室にて。
それ以外はメールでアポイントを取ること。

グラフ、ネットワークは情報科学の様々な分野で非常に大きな役割を果たしています。この分野の重要な概念を理解し、活用できるようになりましょう。

なし