アルゴリズムの設計

記号は前節と同じとし

\[
  i=|\intersection _{B\in {\cal B}}B|,\;
  u=|\union _{B\in {\cal B}}B|
\]

とおく。

$i > 0$のとき、${\cal M}$の$\intersection _{B\in {\cal B}}B$に対応する列は全成分が$1$であり、それを取り除くと基すべての共通部分が空であるようなマトロイドに対応する行列が得られる。逆にそのようなマトロイドを表わす行列に必要なだけ$1$のみからなる列を追加すれば、元のマトロイドと同型なマトロイドに対応する行列を得る。

また$u < m$のとき、${\cal M}$の$E\setminus\union _{B\in {\cal B}}B$に対応する列は全成分が$0$であり、それを取り除くと基すべての合併が全体集合に一致するマトロイドを表わす行列が得られる。逆にそのようなマトロイドに対応する行列に必要なだけ$0$のみからなる列を追加すれば、元のマトロイドと同型なマトロイドを表わす行列を得る。

以上のことから、 $i=0,\,u=m$の場合が本質的であり、それ以外の場合はこの場合から容易に得られることがわかる。

以下$i=0,\,u=m$の場合のマトロイドを数え上げるためのアルゴリズムの設計方針を述べる。 $i=0$という仮定と基の公理の1つによって、任意の基$B$とその任意の元$e$に対して、$e$を$B$以外のある元に置き換えて得られる基が存在し、また全ての基はこのような1個だけの元の置き換えを繰り返して得られることがわかる。

そこで各基$B$に対して、「1個だけの元の置き換え」によって得られる基を特別視して、次のような量を定める。

\begin{eqnarray*}
  \deg B     & := & |\{B'\in {\cal B};|B\setminus B'|=1\}|,\\
  \deg_e B   & := & |\{B'\in {\cal B};B\setminus B'=\{e\}\}|\ \textop{for}\ e\in B,\\
  \deg^-_e B & := & |\{B'\in {\cal B};B'\setminus B=\{e\}\}|\ \textop{for}\ e\not \in B.
\end{eqnarray*}

同型なマトロイドをできるだけ生成しないように、以下のような制限を設ける (そうしても一般性を失わない)。

$\deg$が最大の基は、$B_0=\{0,1,\ldots,r-1\}$.
$\deg_0 B_0\ge\deg_1 B_0\ge\ldots\ge\deg_{r-1} B_0 > 0$.
$\deg^-_r B_0\ge\deg^-_{r+1} B_0\ge\ldots\ge\deg^-_{m-1} B_0$.

このようにすると、 ($\deg_0 B_0,\deg_1 B_0,\ldots,\deg_{r-1} B_0$)と ($\deg^-_r B_0,deg^-_{r+1} B_0,\ldots,\deg^-_{m-1} B_0$)が、 $\deg B_0$の分割になっていることに注意する。

そこで$\deg B_0$の$r$個の正整数への分割をすべて求め、その各々の場合について、 $B_0$から「1個だけの元の置き換え」により得られる集合を上の規則をみたすように構成する。以下新しく得られた基(の候補)の各々に対して、$\deg$が$\deg B_0$を超えないように注意しつつ、「1個だけの元の置き換え」を再帰的に実行して行くことにより、すべてのマトロイドを数え上げる。

$\deg$に注目することにより、 2つのマトロイドが同型でないことの判定が幾分高速化されることにも注意する。