閉路によるマトロイドの定義

マトロイド$M=(E,{\cal I})$は独立集合で定義されているものとする。 $E$の部分集合が独立でないとき従属(dependent)であるという。 極小従属集合を閉路と呼ぶ。

$M(G)$がグラフ$G$の閉路マトロイドならば、 $M(G)$の閉路は$G$の閉路であり、逆に$G$の閉路は$M(G)$の閉路である。

$E$の部分集合が独立であるための必要十分条件は、閉路を含まないことである。

定理[閉路]

閉路の全体${\cal C}$は以下の2条件をみたす。

1. ${\cal C}$の相異なる2元$C_1,C_2$に対して、$C_1\not\subset C_2$。
2. ${\cal C}$の相異なる2元$C_1,C_2$と$e\in C_1\intersection C_2$に対して、 ${\cal C}$の元$C_{3}$で、$C_1\union C_2$に含まれ$e$を含まないものが存在する。

実は マトロイドは閉路を与えることによっても定義することができ て、 しかもその定義は独立集合による定義と (従って基による定義とも)同値である。

つまり有限集合$E$と、その部分集合の族${\cal C}$で上の2条件をみたすものの 対$(E,{\cal C})$に対して、${\cal C}$の元を含まない$E$の部分集合全体を${\cal I}$とすると、 $(E,{\cal I})$は独立集合によるマトロイドの公理をみたし、 その閉路の全体は${\cal C}$に一致す る。