平成18年度

授業科目					担当教員				開講期
グラフ理論					井門　英司				後期
科目番号					対象学年				必修・選択の別		単位数
62140					電子工学専攻				選択		2単位
授業概要 節点と枝で構成される無向グラフ、有向グラフを定義する。これらのグラフにおいて、道、閉路、連結性、木などの基礎的な概念を説明し、最近の応用的な話題とグラフおよびネットワークにおける代表的な探索法を紹介する。また、課題に対するレポート提出を通して、理解を深める。 　　到達目標 　　　・通信網、社会構造などを、無向グラフ、有向グラフまたはネットワークでモデル化できること。 　　　・グラフやネットワークにおいて、道、閉路、連結性、木などの基礎的な概念を説明し、例示できること。 　　　・道、閉路、連結性、木などの基礎的な概念を、最近の応用的な話題に適用できること。 　　　・グラフおよびネットワークにおける代表的な探索法を適用できること。
教科書 シリーズ/情報科学の数学　グラフ理論　　恵羅　博、土屋守正　共著　（産業図書） 参考書 情報システムの基礎　　翁長健治　他著　　（朝倉書店） コンピュータアルゴリズム全科　　千葉則茂　他著　　（啓学出版） 演習グラフ理論　−基礎と応用ー　伊里正夫　他著　（コロナ社） グラフ理論とネットワーク　基礎と応用　　G.R.バサッカー、T.L.サーティ　著　（培風館）
授業の進め方 教科書の項目を選択し、関連する最近の話題を交える。また、次週に提出すべき課題レポートを9〜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）定期試験、臨時試験を同等に評価　70% （2）提出物（9〜10回程度のレポート）　30%
学生へのメッセージ （1）グラフ理論は、電気・電子・情報系学科に共通な内容を含む科目です。 （2）グラフやネットワークは、電気回路網における素子の接続関係、通信網の局と回線の接続関係の表現にとどまらず、社会システムや分子構造などにおける接続関係を表現する場合にも利用できるので、これらの解析にも有用です。 （3）グラフ・ネットワークを実際に取り扱うには、それを表現する適当なデータ構造を用いてプログラミングします。
学習・教育目標 (生産工学)				学習・教育目標 (システムデザイン工学)			B-1	学習・教育目標 (生物応用化学)