용어 목록 > 매트로이드 (Matroid)

매트로이드 (Matroid)

쉽게 풀면

벡터들의 선형독립 개념과 그래프에서 사이클을 만들지 않는 변들의 집합은 서로 달라 보이지만 같은 규칙을 따릅니다. 부분집합도 독립이고, 크기가 다른 두 독립집합이 있으면 작은 쪽에 원소를 더해 키울 수 있다는 규칙입니다. 이런 규칙만 남겨 추상화한 것이 매트로이드입니다.

왜 중요한가

매트로이드 구조가 있으면 욕심쟁이 알고리즘이 항상 최적해를 준다는 정리가 성립하여, 최소신장나무 알고리즘이 왜 옳은지를 근본적으로 설명해 줍니다. 조합최적화에서 알고리즘의 정당성을 판별하는 기준으로 쓰이며, 부호이론과 조합기하에도 응용됩니다.

논문에서는 이렇게 쓰입니다

조금 더 깊게 보면

극대 독립집합을 기저라 하며 모든 기저의 크기는 같고 이 값이 매트로이드의 랭크입니다. 벡터들의 선형독립에서 나오는 선형매트로이드, 그래프의 숲에서 나오는 그래픽매트로이드가 대표적이며, 두 매트로이드의 공통 독립집합 중 최대를 찾는 매트로이드 교차 문제는 다항시간에 풀립니다. 그러나 세 개 이상의 교차는 일반적으로 어려운 문제가 됩니다.

주의할 점

매트로이드는 행렬을 일반화한 것처럼 들리지만 행렬 자체가 아니라 독립성 관계를 추상화한 집합 구조입니다. 또 모든 매트로이드가 벡터공간에서 실현되는 것은 아닙니다.

관련 용어