グラフ理論

Graph Theory

9963215

野口　健太

Kenta Noguchi

2024年度後期

Second Semester

木曜2限

Thursday, 2nd Period

創域理工学部　情報計算科学科

Department of Information Sciences, Faculty of Science and Technology

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

グラフ理論の基本的な定義や性質を学び、具体例を交えながら理解する。

情報数学の基礎知識として、グラフ理論の基本を学ぶ。
本学科のディプロマ・ポリシーに定める「学部教育を通じて修得した知識と訓練された思考力をもとに、自然科学・科学技術の分野のみならず社会における多様な情報を論理的に分析し、問題の発見、さらにはその解決に貢献しうる能力」を獲得するための科目である。

１　グラフ理論の用語・定理を理解し、説明することができる。
２　グラフ理論における証明の手法を理解し、活用することができる。
３　ある条件を満たすグラフの具体例を構成することができる。

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

集合の定義と簡単な性質を用いるため、「情報数学１Ａ及び演習」の単位を修得し、知識を得ていることが望ましい。

小テストの実施　Quiz type test

-

予習と復習を合わせて週４時間を目安とする。
特に各回の講義内容の復習を重点的に行うこと。

中間試験30%、到達度評価・定期試験70%の割合で評価を行う。
[フィードバックの方法]
・中間試験は採点のうえ、返却する。

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

Y

[教科書]「例題で学ぶグラフ理論」　安藤清・土屋守正・松井泰子著　森北出版、2013年発行、978-4627052819

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

[参考書]「曲面上のグラフ理論」　中本敦浩・小関健太著　サイエンス社、2021年発行、978-4781915302

※開講順序や内容は変更の可能性があります。

１　グラフ理論の用語の定義
　用語と定義を覚え、使えるようになる。
２　握手補題、奇点定理
　簡単な定理を学ぶ。
３　オイラー回路
　一筆書きの必要十分条件を理解する。
４　木・全域木（１）
　部分構造としての木の重要性を理解する。
５　木・全域木（２）
　Kruskal および Prim のアルゴリズムにより最小全域木を求める。
６　サイクル・パス（１）
　良い性質を持ったサイクルやパスを探す。
７　サイクル・パス（２）
　Dijkstra のアルゴリズムにより最短パスを求める。
８　これまでのまとめ
　これまでの結果を振り返り、理解度を中間試験により評価する。
９　マッチング（１）
　Hall の結婚定理を理解し、良い性質を持ったマッチングを探す。
10　マッチング（２）
　マッチングを数え上げる方法を理解する。
11　グラフの辺彩色
　問題を理解し、具体例を構成できる。
12　グラフの頂点彩色
　問題を理解し、具体例を構成できる。
13　平面的グラフ（１）
　グラフを図形的に理解し、Euler の公式を計算できる。
14　平面的グラフ（２）
　平面的グラフと頂点彩色の関係を理解し、四色定理を説明できる。
15　到達度評価
　これまでの理解度を到達度評価・定期試験により評価し、まとめを行う。

[ ]内は準備学習（以下「準備」）、復習に必要な時間の目安
１（準備）[１時間]　「情報数学１A及び演習」の内容を復習する。
　（復習）[１時間]　用語と定義を復習し、書く。
２（準備）[１時間]　教科書の該当ページに目を通しておく。
　（復習）[１時間]　グラフを具体的に描き、定理が成り立っていることを確かめる。
３（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　グラフを具体的に描き、定理が成り立っていることを確かめる。
４（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　木の定義を書き、頂点数が少ない木を全列挙する。
５（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　アルゴリズムに従い最小全域木を求める練習をする。
６（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　サイクル・パスの定義を書き、グラフのサイクル・パスを列挙する。
７（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　アルゴリズムに従い最短パスを求める練習をする。
８（準備）[４時間]　これまでの内容をおさらいし、問題を解く。
　（復習）[２時間]　中間試験を解き直す。
９（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　グラフを描き、各サイズのマッチングを全列挙する。
10（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　効率的なマッチングの数え上げの練習問題を行う。
11（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　マッチングとの関係を考え、問題を解く。
12（準備）[２時間]　グラフを描き、辺彩色を何通りも構成する。
　（復習）[２時間]　グラフの辺彩色との違いを考え、問題を解く。
13（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　平面グラフを具体的に描き、Euler の公式を計算する。
14（準備）[２時間]　教科書の該当ページに目を通しておく。
　（復習）[２時間]　平面グラフを具体的に描き、４色で頂点彩色する。
15（準備）[４時間]　これまでの内容をおさらいし、問題を解く。
　（復習）[２時間]　到達度評価・定期試験を解き直す。

-

-

-

特になし

N

N