매트로이드(matroid)란 다음 성질을 만족하는 구조이다. $M =(X, I)$인 매트로이드 $M$이 존재한다고 하자. 1. $X$ 는 유한집합이다. 2. $I$는 $X$의 부분집합이면서 independent set이다. 공집합은 independent set이다. 3. $A, B$가 independent일 때 $|A| < |B|$이면 $x \in B-A$에 대해 $A \cup \{x\}$도 independent인 $x$가 존재한다. 위와 같은 성질을 만족하면 매트로이드라고 한다. 1번은 쉽게 이해할 수 있지만 2, 3번에 나오는 independent가 아직 와닿지 않는다. "어떤 규칙" 정도로 이해하고 넘어가자. 예를들어 $X = \{1, 2, 3, 4, 5\}$이고 $I$의 크기가 3보다 작은 집합이..