科目名 Course Title	グラフ理論［21C1171］ Graph Theory
科目区分・科目種	数学科	クラス	数学科
コンピテンシー		ｶﾗｰｺｰﾄﾞ
単位数	2.0単位	履修年次	2年

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

受講条件・その他注意

2021年度は基本的にZoomを用いたオンラインで行います。対面が指定された週には教室でスクリーンを見ながら聴くこともできますが、配信が他の回と同じ状態になるように講義しますので、教室で聴いてもzoomで聴いてもあまり変わらないと思います。自宅、計算機室、教室など都合の良い場所から出席してください。数学は、テレビを観るように眺めて聞き流しているだけでは理解するのが難しいと思います。ノートをとり、演習問題は積極的に解いて、できるだけ参加するようにしてください。スマホだけで履修する場合は画面が小さいため理解が難しい場合があります。なるべく教科書を用意し、ＰＤＦで事前に配布する資料は印刷するかノートに写して、書き込みながら聴くようにしてください。履修者のカメラの設定はオフで顔が映ることはありません。マイクは通常はミュートし、必要なときだけ解除するようにしてください。Zoomの接続先はmoodleに掲載します。セキュリティ上の理由から、SNS等への転載はしないようにしてください。

授業の形態
講義，一部対面授業あり

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

評価方法・評価割合
小論文（レポート）=70，授業への参加態度=30

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

授業計画

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

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

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