グラフ理論[20C1171]

科目名
Course Title
グラフ理論[20C1171]
Graph Theory
科目区分・科目種 数学科 クラス 数学科
コンピテンシー
カラーコード
単位数 2.0単位 履修年次 2

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

受講条件・その他注意
2020年度はZoomを用いたオンラインで行います。自宅、計算機室、教室など都合の良い場所から出席してください。Zoomのチャット欄に演習問題の解答を書き込んだりして参加していただきますので、使い方を確認しておいてください。
数学は、テレビを観るように眺めて聞き流しているだけでは理解するのが難しいと思います。ノートをとり、演習問題は積極的に解いて、できるだけ参加するようにしてください。スマホだけで履修する場合は画面が小さいため理解が難しい場合があります。なるべく教科書を用意し、PDFで事前に配布する資料は印刷するかノートに写して、書き込みながら聴くようにしてください。
履修者のカメラの設定はオフで顔が映ることはありません。マイクは通常はミュートし、必要なときだけ解除するようにしてください。ずっとミュートでも大丈夫ですので、イヤホンで計算機室などの音を出せない環境からの履修することも可能です。
Zoomの接続先はmoodleに掲載します。セキュリティ上の理由から、SNS等への転載はしないようにしてください。

授業の形態
講義

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

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

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

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

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

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