매트로이드 마이너

매트로이드 이론에서 매트로이드 마이너()는 주어진 매트로이드에서 일부 원소를 “삭제”하거나, 일부 원소를 “축약”하여 얻어지는 매트로이드이다. 그래프 마이너의 일반화이다.

 정의 
(유한 또는 무한) 매트로이드 가 주어졌다고 하자. 그렇다면, 그 부분 집합 에 대하여,

역시 매트로이드를 이룬다. 이를 의 로의 제한이라고 한다. (즉, 이 과정은 의 삭제()이다.)
증명:
로 놓자.
(유한 또는 무한) 매트로이드의 네 공리들은 다음과 같이 확인할 수 있다.
 (I1) : 자명하게 참이다.
 (I2) 만약 일 때, 이므로 이다.
 (IM) 임의의  및 에 대하여, 는 매트로이드의 공리에 따라 극대 원소를 갖는다.

유일하게 자명하지 않은 것은 공리 (I3)이다.

임의의 , 가 주어졌다고 하자. 그렇다면, (IM) 공리를 사용하여,

를 찾을 수 있으며, 이므로

이다.

(I3) 공리를 거듭 사용하여,

인 을 찾을 수 있다.

이제,

를 보이면 족하다. 이 가운데 유일하게 자명하지 않은 것은 이며, 그 증명은

이다.

(유한 또는 무한) 매트로이드 가 주어졌다고 하자. 그렇다면, 그 부분 집합 에 대하여, 쌍대 매트로이드의 제한의 쌍대 매트로이드

를 정의할 수 있다. (는 멱집합이다.) 이는 매트로이드를 이루며, 이를 의, 로의 축약()하여 얻는 매트로이드라고 한다. (즉, 이 과정은 의 축약이라고 한다.)

축약과 제한을 거듭 사용하여 얻는 매트로이드

를 의 마이너라고 한다.

 성질 
 그래프와의 관계 
그래프 마이너는 매트로이드 마이너의 특수한 경우이다. 구체적으로, (유한 또는 무한) 그래프 의 (유한형) 순환 매트로이드를 라고 하자.

또한, 임의의 변의 집합

이 주어졌다고 하자.

그렇다면, 다음이 성립한다.

즉,
 그래프에서 에 속하지 않는 변들의 삭제는 순환 매트로이드에서 에 속하지 않는 원소들의 삭제와 같다.
 그래프에서 에 속하지 않는 변들의 축약은 순환 매트로이드에서 에 속하지 않는 원소들의 축약과 같다.
 그래프에서, 홑 꼭짓점(아무 변과 결합하지 않는 꼭짓점)의 삭제는 그 순환 매트로이드에 영향을 주지 않는다.

이에 따라, 그래프의 순환 매트로이드의 매트로이드 마이너는 그래프 마이너의 순환 매트로이드이다.

 정렬 원순서가 아님 
유한 그래프의 그래프 마이너 관계는 정렬 원순서를 이룬다 (로버트슨-시모어 정리). 즉, 유한 그래프의 순환 매트로이드들로 국한하였을 때, 매트로이드 마이너 관계는 정렬 원순서를 이룬다.

그러나 모든 유한 매트로이드의 집합 위에서, 매트로이드 마이너 관계는 정렬 원순서를 이루지 못한다.

 각주 




 외부 링크 


분류:매트로이드 이론