매트로이드

최근 편집: 2020년 6월 12일 (금) 15:48

매트로이드 Matroid

개요

선형독립을 조합론적으로 정의한 개념. 보다 자세히 알고 싶은 사람은 다음 링크를 참고하자.

정의

어떤 유한 집합 (의 멱집합을 의미한다.)에 대해 가 매트로이드 임은 다음을 만족함을 의미한다:

  1. (유전성, hereditary) 이고 이면
  2. (추가성, augmentation property) 이고, 이면, 어떤 가 존재해

매트로이드도 그래프와 마찬가지로 가중치를 부여해 생각할 수도 있다. 이 경우, 의 각 원소에 실수만큼 가중치를 주고, 의 각 부분집합의 가중치는 해당 부분집합의 원소들의 가중치의 합으로 생각해주면 된다. 대개 의 가중치를 로 표기한다.

예시

벡터 매트로이드

상의 행렬 가 있다고 하자. 의 부분집합 에 대해 에 속하는 열만을 택해 만든 새로운 ( 크기의) 행렬이라 하자. 으로 정의할 경우, 는 매트로이드가 된다.

증명은 추가 바람.

그래프 매트로이드

그래프 [* 단순 그래프일 필요는 없다.]가 주어졌을 때, 로 정의하면, 가 매트로이드가 된다.