授業科目				担当教員			開講期
グラフ理論 (Graph Theory)				井門　英司			後期
科目番号				対象学年			必修・選択の別		単位数
62140				2年　電子工学専攻			選択 （SE-2）		2単位
授業目標 節点と枝で構成される無向グラフ、有向グラフおよびネットワークに対し、それらの基本的な概念と最近の応用的な話題を講義する。 そして、課題のレポートを通して、グラフおよびネットワークにおける代表的な探索法の概略を習得することを目標とする。
教科書 配布資料 参考書 情報システムの基礎　　翁長健治　他著　　（朝倉書店） コンピュータアルゴリズム全科　　千葉則茂　他著　　（啓学出版） 演習グラフ理論　−基礎と応用ー　伊里正夫　他著　（コロナ社） グラフ理論とネットワーク　基礎と応用　　G.R.バサッカー、T.L.サーティ　著　（培風館）
授業の進め方 （1）講義の途中に問題演習を交える。 （2）次週に提出すべき課題レポートを10回程度課す。
授業内容 1 グラフの定義（節点、枝、無向グラフ、有向グラフ）:レポート1 2 グラフの構造（1）（次数、正規グラフ）:レポート2 3 グラフの構造（2）（完全グラフ、2部グラフ）:レポート3 4 連結性（道、閉路、連結成分）:レポート4 5 連結グラフの連結度、オイラーグラフ、ハミルトン閉路:レポート5 6 グラフの木とその列挙:レポート6 7 木の個数:レポート7 8 グラフの平面性と双対グラフ 9 中間試験 10 グラフおよびネットワークの探索 11 深さ優先探索法（DFS）とパス探索:レポート8 12 幅優先探索法（BFS）と最小全域木の探索、最短経路探索:レポート9 13 ネットワークと最大フロー最小カット定理 14 増分可能道の探索と最大フロー（ラベル法）:レポート10 15 期末試験
成績評価の方法 （1）中間試験、期末試験の評価　　60% （2）提出レポートの評価（10回程度）　　40%
学生へのメッセージ （1）グラフ理論は、電気・電子・情報系学科に共通な基礎科目です。 （2）グラフやネットワークは、電気回路網における素子の接続関係、通信網の局と回線の接続関係の表現にとどまらず、社会システムや分子構造などにおける接続関係を表現する場合にも利用できるので、これらの解析にも有用です。 （3）グラフ・ネットワークを実際に取り扱うには、それを表現する適当なデータ構造を用いてプログラミングします。 なお、本科目はJABEEの学習・教育目標（B）に関する能力を培う。
学習・教育目標(デザイン工学)			B		学習・教育目標(生物応用化学)