科目名 Course Title	グラフ理論［26C1171］ Graph Theory
授業言語 Language	Japanese
科目区分・科目種	数学科	クラス	数学科
コンピテンシー	○創造的思考力，○問題解決力	ｶﾗｰｺｰﾄﾞ
単位数	2.0単位	履修年次	2年

担当教員	萩田　真理子
学期	前期
曜日・時限・教室	火曜 5 〜 6 限 理学部2号館507室

授業の形態
講義

教科書・参考文献
丸善出版「ヴァン・リント＆ウィルソン　組合せ論 上巻」著：J. H. van Lint,R. M. Wilson, 監訳：神保雅一，訳：澤正憲，萩田真理子, 2018, ISBN:978-4621302453, 4,290円

ＡＬＨ区分
ＡＬＨ（自発的な学習時間枠）※を実施する

評価方法・評価割合
小論文（レポート）=65，授業への参加態度=15，ALH(自発的な学習時間枠)=20

主題と目標
離散数学の科目で、グラフの定義と性質を紹介します。数学的な定理とその証明の他、実際に使われているアルゴリズムも紹介します。数学では珍しく、予備知識なしにスタートして、半年で最先端の問題まで眺められる分野です。

授業計画

以下のように予定していますが，順番及び内容は変更する場合もあります。 第１回　グラフに関する定義、握手補題 第２回　グラフの同型、部分グラフ、閉路、道及び連結性について 第３回　オイラーグラフとハミルトングラフ 第４回　マッチングと結婚定理 第５回　安定マッチングとゲイルシャプレイのアルゴリズム 第６回【アクティブラーニング】 安定マッチングを求めるゲイルシャプレイのアルゴリズムを用いてマッチングを求めてみましょう。 第７回　アクティブラーニングの問題についての補足と解説、木の性質と数え上げ 第８回　地図の塗り分けとグラフの彩色問題 第９回　平面グラフの性質、5色定理の証明 第１０回　彩色数についてのその他の定理と彩色アルゴリズムについて 第１１回　【アクティブラーニング】 ウェルシュパウエルの彩色アルゴリズムで最小の色数で彩色できないグラフの例を見つけ、そのグラフが最小の色数で彩色されるようにアルゴリズムを改良してみましょう。 第１３回　アクティブラーニングの問題についての補足と解説、ラムゼー問題について 第１４回　重み付きグラフとグラフアルゴリズム。重み最小全域木、ダイクストラアルゴリズムなど 第１５回　グラフのネットワークと最大流最小化カット定理について 以上のように予定していますが、様子を見て変更するかもしれません。

時間外学習
毎週の授業の最後にその日の内容についての簡単な演習問題を配ります。次の授業で解説しますが、時間内に終わらなかった部分は時間外に考えてみてください。

学生へのメッセージ
離散数学の科目で、グラフの定義と性質を紹介します。数学的な定理とその証明の他、実際に使われているアルゴリズムも紹介します。数学では珍しく、予備知識なしにスタートして、半年で最先端の問題まで眺められる分野です。

学生の問い合わせ先
moodleに記載します