全学共通科目講義（１回生～４回生対象）
|
| 現代の数学と数理解析 |
| ―― 基礎概念とその諸科学への広がり |
| |
| 日時： | ２００９年４月２４日（金） １６：３０－１８：００ |
| 場所： | 数理解析研究所 ４２０号室 |
| 講師： | 来嶋 秀治 助教 |
| 題目： | グラフ彩色とアルゴリズム |
| 要約： |
与えられたグラフに対して、隣接する頂点同士が異なる色になるような彩色をグラフ彩色 と言う。地図の彩色を起源とするこの問題は、例えば染色多項式や2002年に解決された強 パーフェクトグラフ定理などの発展的な多くの話題を生み、離散数学、計算科学の進展に 大きな影響を与えている。また、数学的な興味ばかりでなく、スケジューリング、割り当 て問題など、現実世界への応用も多い。本講ではグラフ彩色について、特に平面グラフを 中心に、アルゴリズムと計算量の視点で眺める。 |
|
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html" | |
