科目名	グラフ理論
単位数	2.0
担当者	知能工学専攻 教授 内田智之
履修時期	後期(第４ターム)
履修対象	２年次以上
講義形態	講義
講義の目的	グラフ理論は、さまざまな分野において諸問題を理論的に定式化するための数学的道具として用いられ、 システム設計やソフトウェア開発者にとって必要不可欠な基礎概念のひとつです。グラフ理論の基礎と グラフ理論に基づく基礎的なアルゴリズムや実際問題への応用例を学ぶことによって、実際問題をグラフを用いた数学問題として 記述できる力および論理的思考力と表現力を身につけることを目的とします。
到達目標	グラフ理論の基礎、グラフ理論に基づく基礎的なアルゴリズムと応用例について理解する。【知識2、技能1】 これらの基礎力をもとに、問題の本質をグラフを用いて浮かび上がらせモデル化できるようになる。【思考力・判断力、表現力】 さらに理解した内容を他者に分かりやすく説明できるようになる。【主体性、協働性】
受講要件	特になし。
履修取消の可否	可
履修取消不可の理由
事前・事後学修	事前・事後学修のために、空欄のある講義資料を講義の１週間前までに配布する。 講義資料を元に、参考書やインターネットを活用して講義内容に関する情報を積極的に収集する事前学修を行い、講義ノートおよび講義資料の整理を通して課題提出による事後学修を適宜行う（週９０分程度）。
講義内容	1.　グラフ理論とは（ガイダンスと 数学的基礎） 2. グラフ理論の基礎（部分グラフ・隣接・接続・同形・点次数） 3. グラフ理論の基礎（ウォーク・トレイル・パス・連結性・サイクルおよびグラフ上の演算） 4. グラフ理論の基礎（いろいろなグラフとグラフの行列表現） 5. グラフの諸性質（パス・サイクル・ウォーク） 6. グラフの諸性質（2部グラフとサイクル） 7. グラフの諸性質（単純グラフの最大辺数と最小辺数） 8. グラフの応用1（最短路問題） 9. グラフの巡回性（オイラーグラフとその特徴づけ） 10. グラフの巡回性（ハミルトングラフとその特徴づけ） 11. グラフの応用2（巡回セールスマン問題と中国人郵便配達問題） 12. 木とその性質 13. グラフの応用3（全域木と幅優先・深さ優先） 14. グラフの平面性 15. グラフの彩色 ※授業の順序は変更することがある。 ※上記とは別に期末試験を実施する．
期末試験実施の有無	実施する
評価方法・基準	定期試験結果を６割、課題の完成度や受講態度等の平常点を４割として総合的に評価する。定期試験では、講義で学んだ事項について正確に理解しているか、数学表現としてグラフを活用できるかなどについて評価する。また、課題の完成度や受講態度等では、総合力が必要となる問題が与えられた時に如何に取り組んだかについて評価する。
教科書等	教科書：船曳、内田他著、「グラフ理論の基礎と応用 (未来へつなぐ デジタルシリーズ 14) 」（共立出版） 参考書：R.J.ウィルソン著、西関隆夫、西関裕子共訳、「グラフ理論入門」(近代科学社) 参考書：J.A.Bondy, U.S.R.Murty著、立花俊一、奈良知恵、田沢新成共訳、「グラフ理論への入門」（共立出版）
担当者プロフィール	グラフアルゴリズムおよびグラフマイニングに関する研究に従事しています。 研究室：情報科学部棟別館5階 502研究室
講義に関連する実務経験
課題や試験に対するフィードバック	授業中に行う演習課題やレポート課題は、授業で模範解答を用いた解説を行う。 期末試験については、試験後にオフィスアワー等を通じて解答を用いた解説を行う。
アクティブ・ラーニング	TBL、振り返り
キーワード	グラフ理論とその応用、グラフアルゴリズム、モデル化
備考	【教職】高一種(数学): 解析学及び幾何学の応用等についての教育の方法及び技術の習得を目指します。 講義内容・課題等に関する個別学習相談は随時受け付けています。