マトロイド

【まとろいど (matroid)】

マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.