KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

組合せ最適化読書会 第13回

id:ir5です.今回はマトロイドについてやりました.
いつもはスライドを作ってプロジェクタで投影してやっているのですが今回は準備が大変なのでホワイトボードでやりました.今後もホワイトボードでやりそうな気がします.
マトロイドというのは大雑把にいうと「線形独立なベクトルの部分集合」や「グラフで森をなすような辺部分集合」や「元の個数がある閾値を超えないような部分集合」に共通するある性質を一般化した概念というもので,抽象的な話が続きます.
議論で扱うものが「集合の集合のようなもの」ばかりで慣れなくてなかなか大変でしたが,基本的な性質は押さえられたんじゃないかなぁと思います.
で,次回はマトロイドの続き… ではなくて,LinearProblemについてやる予定です.これは,本当はマトロイドをやるつもりだったのですがどうもこの先LPと絡んだ話が必要になりそうだったのと,あとそもそもマトロイドをやるよりもLPをやった方が今後のためになりそうな気がしたためです.