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