tkenichi の日記

毒舌皮肉系恥さらし日記

マトロイド(1)

f:id:tkenichi:20091003211530j:image

直接仕事と関係ないことを趣味で学習するのは楽しい。

プログラミング言語とか、数学や物理の概念とか研究とまではいかなくても、概観を得て最先端で何が面白いのかを理解するところまで学ぶことができると楽しい。最近そういうのに飢えていたので、何かいいネタはないかと思っていたのだけれど、マトロイドを調べてみることにする。

名前だけは知っていたし、いろいろな応用があることもおぼろげながらも読んでいたけれど、日本語だとまとまった資料は少ないので調べるだけでも意味がありそう。

まず定義(の一つ)。同値な定義がいろいろあるけれど、Whitney のオリジナルな定義ものを参考にする。

有限集合  E とその部分集合族  {\cal I}

  1.  \emptyset \in {\cal I}
  2.  I \subset J \in {\cal I} \Rightarrow I \in {\cal I}
  3.  I,J \in {\cal I}, |I| < |J| \Rightarrow \exists j \in J \setminus I s.t.  I \cup \{j\} \in {\cal I}

を満たすときに  M = (E,\cal I) をマトロイドという

概念としては、線形空間のベクトルの集合のうち、一次独立な部分集合を抽象化したもの。上の例で言うと  {\cal I} が一次独立な部分集合である。

もう一つの典型的な例は無向グラフから得られる。

線形代数グラフ理論はどちらも好きな分野だが、それが隣接行列を通じたもの以外に概念としてつながっているのが面白い。