【投稿日】2013.7.17
日時: | 2013年7月17日㈬ 15:00−17:00 |
---|---|
場所: | 青葉山キャンパス 学際科学フロンティア研究所 大セミナー室 |
世話人: | 宮田洋行 |
15:00−15:50
平井 広志 氏 (東京大学大学院 情報理工学系研究科)
多品種フローと距離空間
ネットワークの入口から出口まで,どれだけ沢山のフローを流すことができるか? この素朴な問題を定式化したものが 最大フロー問題と呼ばれる最も基本的な組合せ最適化問題である. 講演では,古典的なFord-Fulkersonの最大フロー最小カット定理から始めて, 複数の異なる品種のフローが流れる状況を扱う多品種フロー問題への一般化について論ずる. 特に,フローとメトリック(距離)の間にある双対性や, タイトスパン(tight span)と呼ばれる非凸な多面体を用いて 多品種フローを解析する手法について述べたい.予備知識は仮定しない.
16:10−17:00
谷川 眞一 氏 (京都大学 数理解析研究)
グラフの剛性の組合せ的特徴付けについて
ユークリッド空間内に埋め込まれたグラフの各辺を棒材,各頂点を節点と捉えることでグラフの剛性を定義することが出来る.2次元の場合,Maxwellの条件によってグラフの一般剛性が組合せ的に特徴付け出来ることがLamanによって1971年に示された.しかしながら3次元以上の場合においてはMaxwellの条件は十分ではなく,特に3次元剛性の組合せ的特徴付けは剛性理論における重要な未解決問題である. 本講演では,グラフ剛性の基本的性質を解説し,3次元剛性に関する講演者の最近の成果や近年活発に研究が行われている対称性を有するグラフの剛性についても紹介する.