科目名 Course Title	グラフ理論［24C1171］ 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

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

授業計画

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

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

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

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