科目名 グラフ理論概論
単位数 2.0
担当者 知能工学 准教授 内田 智之
履修時期 後期
履修対象 2年次
概要 グラフ理論は、さまざまな分野において諸問題を理論的に定式化するための数学的道具として用いられ、
システム設計やソフトウェア開発者にとって必要不可欠な基礎概念のひとつである。グラフ理論に基づいた
典型的なアルゴリズムや実際問題への応用例を取り上げ、実際問題をグラフを用いた数学問題として
捉えることができる力および論理的思考力と表現力の育成を目的とする。講義の授業形態で行う。
科目の到達目標 数学的表現としてのグラフに関する知識を修得する。また、グラフの活用例について学ぶことにより、より高い論理的思考力とより実効的な表現力を身に付ける。
受講要件 特になし。
事前・事後学修の内容 事前・事後学修のために、空欄のある講義資料を1週間前に配布する。さらに、適宜課題を課す。
講義内容 1. グラフ理論とは(ガイダンスと 数学的基礎)
2. グラフ理論の基礎(部分グラフ・隣接・接続・同形・点次数)
3. グラフ理論の基礎(ウォーク・トレイル・パス・連結性・サイクルおよびグラフ上の演算)
4. グラフ理論の基礎(いろいろなグラフとグラフの行列表現)
5. グラフの諸性質(パス・サイクル・ウォーク)
6. グラフの諸性質(2部グラフとサイクル)
7. グラフの諸性質(単純グラフの最大辺数と最小辺数)
8. グラフの応用1(最短路問題)
9. グラフの巡回性(オイラーグラフとその特徴づけ)
10. グラフの巡回性(ハミルトングラフとその特徴づけ)
11. グラフの応用2(巡回セールスマン問題と中国人郵便配達問題)
12. 木とその性質
13. グラフの応用3(全域木と幅優先・深さ優先)
14. グラフの平面性
15. グラフの彩色
評価方法 定期試験結果を6割、課題の完成度や受講態度等の平常点を4割として総合的に評価する。定期試験では、講義で学んだ事項について正確に理解しているか、数学表現としてグラフを活用できるかなどについて評価する。また、課題の完成度や受講態度等では、総合力が必要となる問題が与えられた時に如何に取り組んだかについて評価する。
教科書等 教科書:船曳、内田他著、「情報系工学のためのグラフ理論」(共立出版)
参考書:R.J.ウィルソン著、西関隆夫、西関裕子共訳、「グラフ理論入門」(近代科学社)
参考書:J.A.Bondy, U.S.R.Murty著、立花俊一、奈良知恵、田沢新成共訳、「グラフ理論への入門」(共立出版)
担当者プロフィール 機械学習研究室に所属し、グラフアルゴリズムおよびグラフマイニングに関する研究に従事しています。
講義内容・課題等に関する個別学習相談は随時受け付けています。
備考 講義中に事前・事後学修のための資料を順次配布します。
【教職】高一種(数学)の選択科目です。解析学及び幾何学の応用等についての教育の方法及び技術の習得を目指します。