매트로이드 임베딩

Matroid embedding

결합학에서 매트로이드 임베딩은 세트 시스템(F, E)이며, 여기서 F는 실현 가능한 세트의 집합체로서 다음과 같은 특성을 만족한다.

  1. (Accessibility Property) 모든 비실용성 집합 X는 X\{x}가 실현 가능한 요소 x를 포함한다.
  2. (확장성 속성) 기준의 모든 실현 가능한 부분 집합 X에 대해(즉, 최대 실현성 집합) B에 대해, B에 있지만 X에 포함되지 않는 일부 요소는 X의 확장 ext(X)에 속하며, 여기서 ext(X)는 X에 없는 모든 요소의 집합이므로 X에 해당되지 않는다.
  3. (Closure-Consurance Property) 실행 가능한 집합 X와 ext(X)의 분리 가능한 모든 상위 집합 A에 대해, A∪{e}는 e의 전부 또는 없음 e에 대한 어떤 실행 가능한 집합에 포함되어 있다.
  4. 실현 가능한 집합의 모든 하위 집합의 집합은 매트로이드를 형성한다.

마트로이드 임베딩은 헬만, 모레트&샤피로(1993)가 탐욕스러운 알고리즘으로 최적화할 수 있는 문제를 특성화하기 위해 도입했다.

참조

  • Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993), "An exact characterization of greedy structures", SIAM Journal on Discrete Mathematics, 6 (2): 274–283, CiteSeerX 10.1.1.37.1825, doi:10.1137/0406021, MR 1215233