매트로이드 이론

매트로이드란?

• 탐욕 알고리즘이 최적 해를 가려낼 수 있는 경우인지를 판별할 수 있게 하며, 독립성이라는 성질을 만족하는 수학적 공간

단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서,

어떤 문제의 공간이 매트로이드 구조를 이루면, 탐욕 알고리즘이 최적해를 도출해낼 수 있지만,

탐욕 알고리즘이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다.

탐욕 알고리즘은 꼭 최적해가 아니여도 최적해에 근사한 값을 찾아낼 수 있다는 점에서 유용한 알고리즘이다.

 

 

💡 어떤 유한 집합 n의 부분 집합들의 집합인 𝐼(즉, 𝐼⊆ 2ⁿ)가 아래 성질을 만족하면 집합 𝐼는 Matroid이다.

 

 

매트로이드의 특성

상속성(Heredity)

A∈I이고, B⊆A이면 B∈I이다.

 

증강성(Augmentation)

크기가 다른 두 집합 A,B(|A|<|B|)가 I에 속하면 ,B의 원소이면서 A의 원소가 아닌 것 중에 A에 더해서 I에 속하게 하는

원소가 존재한다.

교환성(Exchange)

A,B∈I에 대해 어떠한 b∈B−A이든, A∪{b}−{a}∈I가 되는 a∈A−B가 존재한다.

 

포화집합

매트로이드 𝐼⊆2𝑆 와 𝐴∈𝐼 에서 𝐴가 더 이상 확장될 수 없으면, 𝐴는 포화 집합 이다.

 

 

 

 

가중치 매트로이드

매트로이드 𝐼의 원집합 𝑆의 원소들이 양의 가중치를 가지면, 𝐼는 가중치 매트로이드이다.

 

 

 

 

 

 

 

인접성

임의의 해 𝐴,𝐵∈𝐼 에 대해, 𝐵=(𝐴∪{b})−{a} 이고,

𝑎∈𝐴,𝑏∈𝐵−𝐴 이면, "B는 A에 인접하다."라 표현한다.