線型空間の有限部分集合の一次独立な部分集合の全体と、 グラフの閉路を含まない部分グラフの全体は、ある共通の性質をもつ。 この性質を抽象化して得られる概念をマトロイドと呼ぶ。 以下ではマトロイドに関して学習してきたことを、 特にグラフ理論との関係に重点を置いて報告する。 その応用として、マトロイドを数え上げるコンピュータプログラムについても述べる。
始めにグラフの用語を定義する。 次にマトロイドの定義を与える。 最後にマトロイドを数え上げるための コンピュータプログラムについて述べる。 なお以下で、有限集合$A$の個数を$|A|$と書く。
ここではWilsonの教科書に基づいて、 グラフの用語や基礎的な概念を導入する。
マトロイドの定義は、複数の同値なものが存在する。 それらを以下で与え、関連する基本的な性質を示す。
上で紹介した結果の応用と確認のために、マトロイドを数え上げる コンピュータプログラムを構成する。