マトロイド(1)
直接仕事と関係ないことを趣味で学習するのは楽しい。
プログラミング言語とか、数学や物理の概念とか研究とまではいかなくても、概観を得て最先端で何が面白いのかを理解するところまで学ぶことができると楽しい。最近そういうのに飢えていたので、何かいいネタはないかと思っていたのだけれど、マトロイドを調べてみることにする。
名前だけは知っていたし、いろいろな応用があることもおぼろげながらも読んでいたけれど、日本語だとまとまった資料は少ないので調べるだけでも意味がありそう。
まず定義(の一つ)。同値な定義がいろいろあるけれど、Whitney のオリジナルな定義ものを参考にする。
有限集合 とその部分集合族 が
- s.t.
を満たすときに をマトロイドという
概念としては、線形空間のベクトルの集合のうち、一次独立な部分集合を抽象化したもの。上の例で言うと が一次独立な部分集合である。
もう一つの典型的な例は無向グラフから得られる。