Tadachika Oki の日記

私の日々の雑感です。https://sites.google.com/site/tadachikaoki0/

WWW 上のマトロイド関連の資料の紹介

はじめに

WWW上で見つけたマトロイド関連の資料をご紹介します。

(この記事は、僕のはてなダイアリーに以前記載していたものを若干修正しています。)

マトロイドとは何か。

歴史は「James Oxley, WHAT IS A MATROID?」を参考に、
定義はORWikiのマトロイドの項目を参考に書きます。

歴史

マトロイドは、Whitney が1935年に「線形代数とグラフ理論の独立・従属の概念を統一的に扱うため」に導入しました。
また、同じく1935年に中澤武雄もマトロイドを見つけ出しました。
詳しくは http://atelieraterui.blogspot.jp/2010/11/7.html をご覧ください。
以後、特に、離散数学、および離散最適化の分野で長く取り扱われています。

定義

マトロイドは以下で紹介する公理系を満たすように定義されます。
公理系の例として、「独立集合族の公理」、「交換公理」、「階数関数の公理」等があります。
ここでは、この中から代表して「独立集合族の公理」を説明します。

有限集合 Nとその部分集合族 \mathcal{I}が以下の公理系を満たすとき、
(N, \mathcal{I})はマトロイドと呼ばれます。また、この公理系は「独立集合族の公理」と呼ばれます。

(I0) \emptyset \in \mathcal{I}
(I1) I \subseteq J \in \mathcal{I} \Rightarrow I \in \mathcal{I}
(I2) I, J \in \mathcal{I}, | I| < | J| \Rightarrow \exists j \in J \backslash I: I \cup \{ j \} \in \mathcal{I}

（以降、追記します。）

マトロイドの資料

入門

-室田 一雄, 線形独立性とマトロイド, http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-kisosuri/matroid041214.pdf
行列の例を用いて基族とサーキット族によるマトロイドを紹介し、いくつかの公理系についても紹介。
-藤重 悟, 劣モジュラ構造と離散凸性, http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H17-fujishige.pdf
マトロイド、ポリマトロイド、および劣モジュラシステムと一般化の段階を追って説明し、離散凸解析の基礎も紹介。
-James Oxley, WHAT IS A MATROID?, http://www.math.lsu.edu/~oxley/survey4.pdf
マトロイドの公理系、マトロイドの例、マトロイドの操作、マトロイドと組合せ最適化、禁止マイナー、および正則マトロイドの分解の説明。

その他関連する話題 

-谷川眞一, グラフの剛性とマトロイド, http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H24-tanigawa.pdf

- G, M, Ziegler, Oriented Matroids Today, http://cs.anu.edu.au/publications/eljc/Surveys/ds4.pdf
-Matroidとoriented matroid, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid.html
-Matroidとoriented matroidの基本, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_basics.html

- 藤重 悟,
離散凸関数のお話,
(ファイル形式: PDF) http://www.kurims.kyoto-u.ac.jp/~fujishig/talk/OR-Hokkaido.pdf

デルタマトロイドに関する資料

デルタマトロイドは、Bouchetが1987年に、ChandrasekaranとKabadiが1988年にそれぞれ提案したマトロイドの一般化です。
マトロイドの交換公理を対称差を用いて緩めることで得られた公理を満たすように定義されます。

ジャンプシステムは、BouchetとCunninghamが1995年に提案したデルタマトロイドの一般化です。

-塩浦昭義,
ジャンプシステム上の最適化問題に対するアルゴリズム,
(ファイル形式: PDF) http://www.dais.is.tohoku.ac.jp/~shioura/talks/slides/d2007-04-14.pdf
内容: ジャンプシステム上での離散凸関数の最小化法が紹介されています。

- Andre Bouchet and Bill Jackson,
Parity Systems and the Delta-Matroid Intersection Problem,
(ファイル形式: PDF) http://www.combinatorics.org/Volume_7/PDF/v7i1r14.pdf

- Andre Bouchet, William H. Cunningham,
Delta-matroids, Jump Systems and Bisubmodular Polyhedra,
(CiteSeerX へのリンク) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4680

- Ando Kazutoshi, Fujishige Satoru, Naitoh Takeshi,
A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON,
(CiNii へのリンク) http://ci.nii.ac.jp/naid/110001184398

- László Lovász, The Membership Problem in Jump Systems
(CiteSeerX へのリンク) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.2094

- Akiyoshi, Shioura,
Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra,
(ファイル形式: PDF) http://www.dais.is.tohoku.ac.jp/~shioura/papers/neighbor-system.pdf

その他

-Matroidのデータから構成できるもの, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_invariants.html
-Matroidの応用や関連した分野, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_applications.html
-様々なmatroid, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_variations.html

ORWikiから

ORWikiは、日本オペレーションズ・リサーチ学会が作成しているWikiです。
この中から、マトロイド関連の資料をご紹介します。
-マトロイド, 《マトロイド》 - ORWiki
-最小木問題, 《最小木問題》 - ORWiki
-デルタマトロイド, デルタマトロイド - ORWiki
-付値マトロイド, 付値マトロイド - ORWiki

Wikipediaから

Wikipedia, マトロイド, http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89