グラフ理論

科目名	グラフ理論
旧カリキュラム名	グラフ理論
教員名	安藤　清
単位数	2	学年	2	開講区分	文理学部（他学部生相互履修可）
科目群	情報科学科
学期	前期	履修区分	選択必修

授業テーマ	グラフ理論入門
授業のねらい・到達目標	交通網の路線図やネットワークの結線図のように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な概念である。この講義では、グラフに関するいくつかの話題を取り上げ解説する。受講者がグラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解することを目標とする。
授業の方法	最初の複数回でグラフの基本概念を説明し、その後は各回ごとにひとつの話題と取り上げ講述する。特に教科書を指定することはせず、毎回プリントを配布する。また、毎回の講義の終わりに、その回の講義内容の理解確認の為に小テストを行う。
事前学修・事後学修，授業計画コメント	最初の複数回で学ぶグラフの基本概念はその後の聴講においての必須の知識である。基礎的な概念、定義、用語、記号などの理解に不安のある場合はそれまでの講義プリントおよび毎回の講義で配布される小テストの解答を用いて復習して欲しい。

授業計画
1	グラフの定義と基本的な用語を学ぶ。頂点、辺、次数などの概念を学習する。単純グラフ、多重グラフなどについても学ぶ。
2	近傍と次数の概念を学ぶ。同形の概念を学び、同形判定の基礎事項を理解する。
3	完全グラフ、道、閉路など特殊なグラフの定義とそれらの性質を学ぶ。また２つ以上のグラフから１つのグラフを作り出す演算操作もいくつか学ぶ。
4	深さ優先探索、幅優先探索のアルゴリズムを学ぶ。
5	グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。
6	グラフデータの表現方法を学び、グラフを計算機に格納する方法について学ぶ。
7	グラフの平面性の概念を学び、オイラーの公式を学習する。
8	グラフのオイラー回路を求めるアルゴリズムを学習する。
9	ハミルトングラフについて学ぶ。
10	重み付きグラフを導入し、グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。
11	木の定義を学び、その性質を調べる。重み付きグラフの最小全域木を求めるアルゴリズムについて学ぶ。
12	根付き木の概念を学び、2分探索木を用いた探索アルゴリズムを学ぶ。
13	根付き木を用いた情報圧縮アルゴリズム（ハフマン符号アルゴリズム）を学ぶ。
14	根付き木の一種のヒープを導入し、ヒープを用いた整列アルゴリズム（ヒープソート）を学ぶ。
15	これまで学んできたことの復習と補足を行う。

その他
参考書	加納幹雄『情報科学のためのグラフ理論』朝倉書店 2001年第1版安藤清　土屋守正　松井泰子『例題で学ぶグラフ理論』森北出版 2013年第1版グラフ理論に興味のある学生は最初の参考書を読んでみるとよい。2番目は具体的な例で復習したい学生向けの初等的な参考書である。
成績評価の方法及び基準	試験(90%)、授業内テスト(10%) 各回の小テストとは別に試験を行う。
オフィスアワー	授業内に知らせるアドレスに連絡して下さい。