数理科学談話会
2017年度
第9回
日時：12月22日（金）17:40～18:40
場所：理工学部2号館10階 共通演習室
講演者：藤沢 潤 氏 （慶應義塾大学）
題目：グラフの完全マッチングに関する話題
概要：いくつかの頂点と, その中のいくつかの2点のペアが線で結ばれている構造をグラフと呼びます。 グラフ理論の研究は, 電気回路・集積回路の設計や, プログラミングにおけるアルゴリズムの最適化など, 情報科学の様々な分野への応用がなされています。
グラフのすべての頂点を, 辺で結ばれた2点のペアに分割できるとき, その分割を完全マッチングと呼びます。 本講演では, グラフや完全マッチングに関する基本的な性質から, マッチング拡張問題に関する最新の研究成果まで, 幅広く紹介する予定です。
