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