大学院
過去（2023年度）の授業の情報です
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
数理構造論
Discrete structures in graphs and computational geometry
This course introduces discrete structures in geometric graphs that help the design of efficient algorithms in computational geometry. The main focus is on the interaction between graph theory and geometry.
時間割／共通科目コード
コース名
教員
学期
時限
4820-1008
GIF-MA6208L3
数理構造論
谷川 眞一
木曜2限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
情報理工学系研究科
授業計画
1. Introduction
2. Graph theory basic: Menger's theorem
3. Planar graphs and Kuratowski's theorem
4. Graph drawing, Tutte's rubber band embedding, and connectivity testing
5. Graph Laplacian, electronic flows, and random walks
6. Koebe's coin representation of planar graphs, Riemann mapping theorem, Steiniz's theorem
7. Colin de Verdiere graph paragrameter
8. Orthogonal representations of graphs and semidefinite programming
9. Lovasz theta function, stable sets, vector colorings, and perfect graphs
10. Graph realizations and rigidity
授業の方法
Online (by Zoom)
成績評価方法
Grade by assignments
教科書
Laszlo Lovasz, Graphs and Geometry, AMS, 2019
参考書
Reinhard Diestel, Graph Theory, Springer, 2017
履修上の注意
No Prerequisite
