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