매트로이드

매트로이드라는 개념은 최대 가중치를 갖는 어떤 객체 집합을 골라야 하는 문제에서 일부 탐욕 알고리즘을 고안하고 증명하는 데 필요합니다. 예를 들어 최소 신장 트리, 최대 정점 가중치 매칭, 시간 제약이 있는 주문 처리 등이 있습니다.

추상대수학 전문가가 아니라면, 글 끝에 있는 매트로이드 예시를 수시로 참고하시기를 권장합니다.

#정의

매트로이드란 쌍 $(X, I)$를 말하며, 여기서 $X$는 매트로이드의 기저 집합이라고 불리는 원소들의 집합이고, $I$는 독립 집합族이라고 불리는 $X$의 부분집합들로 이루어진 어떤 집합입니다. 매트로이드는 다음 성질들을 만족해야 합니다:

• 공집합은 독립입니다: $\varnothing \in I$

• 독립 집합의 모든 부분집합 역시 독립입니다:

• 독립 집합 $A$의 원소 수가 독립 집합 $B$의 원소 수보다 적다면, $B$에는 $A$에 추가하여 크기 $|A|+1$의 독립 집합을 만드는 원소가 존재합니다:

매트로이드에 가법적 가중치 함수 $w(A) = \sum w(a_i)$가 주어져 있으면 그 매트로이드를 가중 매트로이드라고 합니다.

#라도-에드먼즈 알고리즘

가능한 한 많은 원소를 포함하면서 동시에 가중치는 가능한 한 작은 독립 집합을 찾아야 한다고 합시다. 원소들을 가중치의 오름차순으로 정렬한 뒤 그 순서대로 답에 추가해 보기만 하면 된다고 주장할 수 있습니다:

X.sort()
s = []
for x in X:
    if good(s + [x]):
        s += [x]

여기서 good은 $s \cup x \in I$를 의미합니다.

임의의 매트로이드에 대한 이 알고리즘의 정확성은 다음 명제로부터 따라 나옵니다:

라도-에드먼즈 정리. $A \in I$가 크기가 $k$인 $X$의 모든 독립 부분집합 중 가중치가 최소인 집합이라고 합시다. $x: A \cup x \in I,;x \notin A,;w(x)$가 최소인 원소를 택합시다. 그러면 $A \cup x$는 크기가 $k + 1$인 $X$의 독립 부분집합 중 가중치가 최소인 집합입니다.

증명:

크기가 $k + 1$인 $X$의 독립 부분집합 중에서 가중치가 최소인 집합 $B$를 생각해 봅시다.

매트로이드의 성질에 의해 $\exists y \in B \setminus A : A \cup y \in I$입니다.

그러면 다음 두 부등식이 성립합니다:

값 $w(A)$는 값 $w(B) - w(y)$를 양쪽에서 제한합니다. 따라서 두 값은 같습니다. 그러므로 $w(A \cup y) = w(A) + w(y) = w(B)$입니다.

따라서 집합 $A$에 $A \cup x \in I$를 만족하는 원소 중 최소인 $x$를 합하면, 크기가 $k + 1$인 $X$의 독립 부분집합 중 최소 가중치를 갖는 집합을 얻습니다.

다시 말해, 최적의 $k$-원소 독립 집합이 있다면, 구성된 집합을 독립으로 유지하는 최소 원소를 그 집합에 추가하여 최적의 $(k+1)$-원소 집합을 귀납적으로 구성할 수 있습니다.

#예시

그리디 알고리즘을 증명하려면 고려하는 집합이 매트로이드라는 것을 보이기만 하면 됩니다(물론 이것이 항상 쉬운 것은 아닙니다). 처음 두 조건은 증명하기가 자명하지만, 세 번째 조건은 더 어렵습니다.

#최소 신장 트리

무향 그래프 $G = (V, E)$를 생각해 봅시다. $I$를 그래프의 숲(즉, $E$의 비순환 부분집합)들의 집합이라고 합시다. 그러면 $M = (E, I)$는 매트로이드입니다.

• 간선이 없는 그래프는 숲입니다.
• 숲에서 간선을 제거해도 여전히 숲입니다.
• 두 숲 $|A| \leq |B|$가 있다고 합시다. $A$에는 $|V| - |A|$개의 연결 요소가 있고, $B$에는 $|V|-|B|$개의 연결 요소가 있습니다. $B$의 연결 요소가 더 적으므로, $A$의 두 연결 요소를 잇는 어떤 간선 $x$가 존재합니다. 바로 그 간선을 택하면 됩니다. $x$는 서로 다른 두 연결 요소를 이었을 뿐이므로 $A \cup {x}$ 역시 숲이 됩니다.

이 매트로이드에 라도-에드먼즈 정리를 적용하면 최소 신장 트리를 찾는 크러스컬 알고리즘의 정당성을 얻습니다.

#스케줄링

$n$개의 작업이 있고, 각 작업을 수행하는 데 $1$시간이 걸린다고 합시다. $i$번째 작업을 $d_i$번째 시간까지 완료했을 때 받는 보상은 $w_i$입니다. 한 시간에는 하나의 작업만 수행할 수 있습니다. 목표는 보상의 합을 최대화하는 것입니다.

마감 기한 전에 모두 끝낼 수 있는 순서가 존재하는 작업 집합을 올바른 집합이라고 부릅시다. 고정된 집합은 다음과 같이 확인할 수 있습니다. 마감 기한($d_i$) 순으로 정렬한 뒤, 모든 $i$에 대해 $d_i \geq i$인지 확인합니다.

그러면 $M =$ (모든 작업의 집합, 올바른 작업 집합들의 집합)은 매트로이드입니다:

• 빈 작업 집합은 항상 수행할 수 있습니다.
• 작업의 수가 줄어들었다면, 그 작업들도 역시 제시간에 해낼 수 있습니다.
• 두 개의 올바른 집합 $|A| \leq |B|$가 있다고 합시다. 그러면 $B$에는 마감 시간이 $|A|$보다 늦은 작업 $x$가 존재합니다. $A$의 모든 작업은 $|A|$번째 시간까지 끝낼 수 있고, $(|A|+1)$번째 시간에는 $x$를 수행하면 됩니다. 따라서 $A \cup x$ 역시 올바른 집합입니다.

따라서 작업을 비용의 내림차순으로 정렬한 뒤 그 순서대로 답에 추가해 보면서, 어떤 자료구조를 사용하여 집합이 올바른지 확인하면 됩니다.

#매칭

이분 그래프 $G = (L, R, E)$를 생각해 봅시다. $I$를 어떤 매칭으로 덮을 수 있는 왼쪽 부분의 정점 집합들의 모임이라고 합시다. 그러면 $M = (L, I)$는 매트로이드입니다.

• 모든 매칭은 공집합인 정점 집합을 덮습니다.
• 원래의 매칭은 원래 정점 집합의 임의의 부분집합도 덮습니다.
• 두 정점 집합 $|A| \leq |B|$가 있다고 합시다. $A$에 대응하는 매칭의 간선을 빨간색으로, $B$에 대응하는 매칭의 간선을 파란색으로 칠하고, 두 매칭 모두에 속하는 간선은 보라색으로 칠합시다. 빨간 간선과 파란 간선으로 이루어진 그래프를 생각해 봅시다. 이 그래프의 모든 연결 요소는 빨간 간선과 파란 간선이 번갈아 나타나는 경로 또는 사이클입니다. 모든 사이클에는 빨간 간선과 파란 간선의 개수가 같은데, 전체적으로 파란 간선이 더 많으므로 파란 간선으로 시작하여 파란 간선으로 끝나는 경로가 반드시 존재합니다. 이 경로에서 빨간색과 파란색을 서로 바꾸고, 보라색 간선을 다시 빨간색으로 되돌립시다. 이제 빨간 간선으로 이루어진 그래프에는 간선이 하나 더 많으므로, 집합 $A$에 이전에 $B$에 속해 있던 왼쪽 부분의 어떤 정점이 추가된 것입니다.

왼쪽 부분의 정점들에 가중치가 있고, 최소 가중치의 최대 매칭을 찾아야 한다고 합시다. 정리에 따르면, 왼쪽 부분의 정점들을 가중치에 따라 정렬한 다음 이들을 매칭에 추가해 볼 수 있습니다. 이는 표준적인 쿤 알고리즘으로 할 수 있습니다.

#선형 독립인 벡터

$n$차원 벡터들의 집합에서 어떤 벡터도 다른 벡터들의 선형 결합(가중합)으로 나타낼 수 없으면, 그 집합을 선형 독립이라고 합니다.

어떤 벡터 집합 $V$를 생각해 봅시다. $I$를 그 집합의 모든 선형 독립인 부분집합들의 집합이라고 합시다. 그러면 $M = (V, I)$는 매트로이드입니다.

• 공집합에서는 어떤 벡터도 만들어 낼 수 없습니다.
• 선형 독립인 집합의 부분집합도 선형 독립입니다. 벡터를 만들어 낼 방법이 더 줄어들었기 때문입니다.
• 두 개의 선형 독립 집합 $A$와 $B$가 있고, $B$가 더 크다고 합시다. 그 집합에서 $A$와 양립하는 벡터를 하나도 고를 수 없다고 합시다. 그러면 $B$의 모든 벡터를 $A$로 표현할 수 있다는 결론이 나옵니다. 따라서 $B$의 차원은 확실히 더 클 수 없으므로 모순입니다.

예제 문제: 각 벡터마다 가격이 매겨져 있을 때, 가중치가 최대인 기저를 구하십시오.

참고: $Z_2$도 공간이므로, 그곳에서도 선형 독립을 정의할 수 있습니다. 이는 「XOR로 0을 만들 수 없는 수들의 최대 집합을 구하는」 식의 문제에도 같은 내용이 적용된다는 뜻입니다.