[Algorithms] Matroid Theory | 매트로이드 이론

Matroid Theory

매트로이드 이론

- Greedy Algorithm(그리디 알고리즘)이 Optimal Solution(최적해)을 가려낼 수 있는 경우인지를
  판별할 수 있게 하는 수학적 공간이다.

 

* Greedy Algorithms (그리디 알고리즘, 탐욕 알고리즘) (URL)

[Algorithms] Greedy Algorithms | 그리디 알고리즘, 탐욕 알고리즘

- 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서,
  어떤 문제의 공간이 매트로이드 구조를 이루면, Greedy Algorithm이 최적해를 도출해낼 수 있지만,
  Greedy Algorithm이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다.

- 원래 Matrix에서 행들의 독립성을 일반화 및 추상화하면서 출현한 탓에 Matroid란 이름을 갖게 되었다.

 

---

Definition (정의)

어떤 유한 집합 \(S\)의 부분 집합들의 집합인 \(I\) (즉, \(I \subseteq 2^S\))가 아래 성질을 만족하면
집합 \(I\)는 Matroid이다.

Property 1. Heredity (상속성)

\(A \in I\) 이고, \(B \subseteq A\) 이면 \(B \in I\) 이다.

- 집합 \(A\)가 \(I\)에 속하면, \(A\)의 모든 부분 집합도 \(I\)에 속한다.
- 공집합은 모든 집합의 부분집합이므로, \(\varnothing \in I\) 를 의미하는 성질이기도 하다.

Property 2-1. Augmentation (증강성)

\(A, B \in I\) 이고, \(|A| < |B|\) 이면, \(A \cup \{x\} \in I\) 인 \(x \in B-A\)가 존재한다.

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

Property 2-2. Exchange (교환성)

\(A, B \in I\) 에 대해 어떠한 \(b \in B-A\) 이든,
\(A \cup \{b\} - \{a\} \in I\) 가 되는 \(a \in A-B\) 가 존재한다.

※ Augmentation과 Exchange는 사실상 같은 의미이다.

 

 

 

Extension (확장)

매트로이드 \(I \subseteq 2^S\) 와 \(A \in I\) 에서
\(A\)에 속하지 않는 어떤 원소 \(x \in S\)에 대해,
\(A \cup \{x\} \in I\) 이면,
"\(x\)가 \(A\)를 Extension(확장)한다."라 표현한다.

 

 

 

Maximum Set (포화 집합)

매트로이드 \(I \subseteq 2^S\) 와 \(A \in I\) 에서
\(A\)가 더 이상 Extension(확장)될 수 없으면,
\(A\)는 Maximum Set(포화 집합) 이다.

 

 

 

Weighted Matroid (가중치 매트로이드)

매트로이드 \(I\)의 원집합 \(S\)의 원소들이 Positive Weight(양의 가중치)를 가지면,
\(I\)는 Weighted Matroid(가중치 매트로이드)이다.

 

 

 

Adjacency (인접성)

임의의 해 \(A, B \in I\) 에 대해 \(B = (A \cup \{b\}) - \{a\}\) 이고,
\(a \in A, b \in B-A\) 이면,
"\(B\)는 \(A\)에 인접하다."라 표현한다.

- 즉, 한 원소의 교환으로 서로 이동 가능한 두 해(포화 집합)을 인접 관계에 있다고 정의한다.

 

 

 

Local Optimum (Attractor; 지역 최적해, 끌개)

임의의 해 \(A \in I\) 에 대해 \(A\)와 품질이 동일한 해들의 인접 관계의 체인을 따라
이를 수 있는 모든 해에서
품질이 더 좋은 인접해가 없으면, \(A\)는 지역 최적해이다.

- 임의의 해 \(A \in I\) 가 봉우리를 형성하면, 이를 지역 최적해라 한다.
  (봉우리는 하나 이상의 해로 구성된다.)
- 인접한 해 중에 \(A\)보다 품질이 좋은 해는 없지만, 품질이 동일한 해가 있다면 \(A\)가 지역 최적해가 아닐 수 있다.
  (품질이 동일한 해들의 인접 관계를 따라가며 품질이 더 좋은 해를 만날 가능성이 있기 때문이다.)
- 이렇게 인접 관계 체인을 따라 형성되는 품질이 동일한 해들 중,
  더 좋은 해가 없으면 이들은 하나의 지역 최적해 봉우리를 이룬다.

* Funnel (퍼널)
- 해들이 깔때기처럼 한 끌개로 강하게 빨려들어 가는 공간 구조를 의미한다.

 

 

 

Global Optimum (전역 최적해, 최적해)

Local Optimum(지역 최적해)를 형성하는 봉우리가 여럿 있을 때,
이 중 가장 품질이 좋은 봉우리를 전역 최적해라 한다.

 

---

Graphic Matroid (그래프에서의 매트로이드)

* Tree (나무)
- Graph의 Subgraph 중 Cycle을 갖지 않는 연결 그래프를 "Tree"라 부른다.

* Forest (숲)
- 하나 이상의 Tree가 모여있는 구조를 "Forest"라 부른다.
- 임의의 Forest는 서로 겹치는 부분이 없는 Tree를 하나 이상 모아놓은 것인데,
  이는 Cycle을 이루지 않는 간선들의 집합이라 달리 표현할 수 있다.
- 또한, Forest는 보통 정점과 간선들로 구성이 되지만,
  정점은 간선을 표현하기 위한 수단으로 생각할 수 있기 때문에
  Forest는 간선들로만 표현할 수 있다.
- 특히, 위 그림 (f)의 Forest는 더 이상의 Extension(확장)이 불가능한 Maximum Set(포화 집합)이다.

 

 

 

Theorem. Graph \(G = (V, E)\)의 Forest 집합 \(F \subseteq 2^E\) 는 매트로이드이다.

pf) \(G = (V, E)\)에서 파생될 수 있는 모든 Forest의 집합을 \(F\)라 하자. (그림 11-2와 같은 다양한 Forest들의 집합)
즉, \(F \subseteq 2^E\) 이다.
\(G\)에서 임의의 Forest는 간선을 최대 \(|E|-1\)개 가질 수 있고 이 경우는 단 하나의 Tree로 구성된 Forest이다.

\(F\)는 매트로이드이다.
\(F\)가 Heredity와Augmentation을 보이고 있음을 증명한다.

Property 1. Heredity
어떤 Forest의 부분 집합도 당연히 Forest이다.

Property 2. Augmentation
\(|A| < |B|\) 인 두 Forest \(A, B\)가 있다 하자.
(\(|A|\) : Forest \(A\)를 구성하는 간선의 개수)
(즉, Forest \(A\)를 구성하는 Tree의 개수 > Forest \(B\)를 구성하는 Tree의 개수)
(간선의 개수와 그에 따른 Tree의 개수는 반비례한다.)
\(B\)는 몰라도, \(A\)는 적어도 2개 이상의 분리된 Tree로 구성되어 있을 것이다.

\(A\)에 속하는 임의의 Tree 하나를 \(T\)라 하자.
\(T\)의 정점들을 연결하는 간선 개수는 \(B\)가 \(A\)보다 적다.
그렇지 않으면, \(B\)에 Cycle이 생기기 때문이다.
(이러한 사실은 \(A\)의 다른 Tree에 적용해도 마찬가지이다.)

\(B\)의 간선의 개수가 \(A\)보다 많으므로,
\(B\)에는 \(A\)의 서로 다른 트리를 연결하는 간선이 적어도 하나 이상 존재하게 된다.
이 간선 중 하나를 \(A\)에 더해도 Cycle을 만들지 않으므로, 여전히 Forest를 이룬다.

Example. Augmentation of Forest

Picture	Description
(a)	- Forest \(A\)를 나타내는 그림으로,   \(|A| < |B|\)이다. - 즉, \(A\)의 간선의 개수가 \(B\)의 간선의 개수보다 적다.
(b)	- Forest \(B\)를 나타내는 그림으로,   \(|A| < |B|\)이다. - 즉, \(B\)의 간선의 개수가 \(A\)의 간선의 개수보다 많다.
(c)	- 굵은 간선은 \(B\)의 간선들 중,   \(A\)의 같은 Tree에 속하는 정점들을 연결하는 간선이다. - 점선 간선은 \(B\)의 간선들 중,   \(A\)의 서로 다른 Tree를 연결하는 간선이다. - \(|A| < |B|\)이므로, 어떤 경우든 점선 간선이 하나 이상 존재한다.
(d)	- Forest \(A\)에 간선 \(e\)를 추가해도, 여전히 Forest를 이룬다. - 이를 두고, "\(e\)는 \(A\)를 Extension(확장)한다."라 표현한다.

 

 

 

Theorem. 임의의 매트로이드 \(I \subseteq 2^S\) 의 Maximum Set(포화 집합)들의 크기는 모두 같다.

pf) 두 포화 집합 \(A, B\)가 서로 다른 크기를 가졌고, \(|A| < |B|\)라 가정하자.
매트로이드의 Augmentation 성질에 의해,
\(A \cup \{x\} \in I\) 인 \(x\)가 \(B-A\)에 존재하여 \(A\)가 Extension(확장)된다.
\(A\)가 Maximum Set이라는 가정에 모순이 발생한 것을 볼 수 있다.
그러므로, 두 포화 집합의 크기는 다를 수 없다.

 

---

Matroid Structure as Greedy Algorithm Perspective (그리디 알고리즘 관점에서의 매트로이드 구조)

- Weighted Matroid에서는 소속된 원소들의 가중치 합을 최대로 하는 부분 집합 \(A \in I\)를 찾는 등의
  최적화 문제를 만들 수 있다.
  (이는 Graphic Matroid에서 간선 가중치의 합을 최대로 하는 Forest를 찾는 것에 해당된다.)
  (이를 "Maximum Spanning Tree 문제"라 이름붙일 수도 있을 것이다.)

* Matroid 구조에 Greedy 알고리즘을 적용하여 최대 가중치 합을 구하는 Pseudo Code

greedy(I, w[])
// I : 원집합 S의 부분 집합
// w[] : 가중치 배열
{
    A = empty_set();
    sort_by_weight_in_descending_order(S);
    
    for(x ∈ S)
        if(A ∪ {x}∈ I)
            A = A ∪ {x};
    
    return A;
}

pf) 위 알고리즘이 항상 Optimal Solution을 도출함을 증명한다.

\(\texttt{greedy(I, w[])}\)로 구한 부분 집합 \(A \in I\)보다
가중치가 큰 부분 집합 \(X \in I\)가 존재한다 가정하자.

가중치가 모두 양수이고,
알고리즘은 더 이상 확장이 가능하지 않을 때까지 원소 추가를 시도하므로,
최종적으로는 Maximum Set(포화 집합)을 갖게 된다.
이 포화 집합의 원소의 개수를 \(n\)개라 하자.
또, 포화 집합 \(A\)의 원소들을 크기 순으로 \(a_1, a_2, \cdots, a_n\) 이라 하고,
\(X\)의 원소들을 크기 순으로 \(x_1, x_2, \cdots, x_n\) 이라 하자.
이 중, \(x_k, a_k\)에서 처음으로 \(w(x_k) > w(a_k)\) 가 된다 하자.

부분 집합 \(A_{k-1} = \{a_1, a_2, \cdots, a_{k-1}\} \in I\),
\(X_k = \{x_1, x_2, \cdots, x_k\} \in I\) 에서
\(|A_{k-1}| < |X_k|\) 이므로
Augmentation에 따라 \(A_{k-1} \cup \{x_i\} \in I\) 인 \(x_i \in X_k - A_{k-1}\) 이 존재한다.

\(w(x_i) \geq w(x_k) > w(a_k)\) 이므로,
\(\texttt{greedy(I, w[])}\)는 \(a_i\) 대신, \(x_i\)를 선택하게 된다.

그러므로, \(A\)보다 가중치가 더 큰 부분 집합 \(X \in I\)가 있으면,
\(A\)가 \(\texttt{greedy(I, w[])}\)의 Output이 될 수 없다.
즉, \(\texttt{greedy(I, w[])}\)는 항상 Optimal Solution을 Output으로 Return한다.

※ 최적의 Maximum Set을 찾는 문제로 제한하면, 최소 합을 구하는 경우에도 위 알고리즘은 항상 최적해를 도출해낸다.
(단, 가중치를 오름차순으로 정렬해야 한다.)

* Constructive Algorithm (구축형 알고리즘)
- 불완전한 상태에서 온전한 최적해로 나아가는 형태로 계산하는 알고리즘을 의미한다.
- 위 알고리즘은 구축형 알고리즘에 해당된다.
  (집합 \(A\)가 공집합에서 점차 최적해에 가까워지기 때문이다.)

* Improvement Algorithm (개선형 알고리즘)
- 알고리즘의 초기부터 온전한 해로 시작하여, 최적해에 가까운 해가 발견되면, 수정해나가는 알고리즘을 의미한다.

---

Matroid Structure as Problem Space Search Perspective (문제 공간 탐색 관점에서의 매트로이드 구조)

- Maximum Set(포화 집합)의 크기가 \(n\)인 매트로이드에서 하나의 해 \(A = \{a_1, a_2, \cdots, a_n\} \in I\) 는
  \(n\)차원 벡터로 표현할 수 있다.
  (즉, 하나의 해를 \(<a_1, a_2, \cdots, a_n>\) 으로 볼 수 있다.)

 

 

 

Constructive Algorithm for Matroid Structure

- 공집합에서 시작하여, 최종적으로 집합에 \(n\)개의 원소를 채우게 된다.
- 원소를 하나씩 채울 때마다 중간해의 차원은 하나씩 낮아진다.
  (해가 하나씩 확정되면서, 경우의 수가 줄어들게 된다.)
- 즉, 처음 공집합 상태에서는 모든 가능한 해를 포함하고 있으므로, 가능한 해는 n차원 전체이고,
  해가 하나씩 확정됨에 따라 벡터의 차원이 하나씩 낮아지게 된다.
- 최종적으로, 마지막 원소가 확정되고 나면 벡터는 하나의 점이 되고, 남은 차원은 없다.

* Hyper Plane (초평면)
- 최적해 벡터에 해를 추가함에 따라 거치는 중간 공간들을 초평면이라 한다.
- 매트로이드 구축형 알고리즘의 진행 과정에서는
  거쳐가는 초평면은 항상 최적해를 포함하고 있고,
  이 초평면을 더 좁혀나가면서 최적해에 해당하는 점을 도출해낸다.

Example. 매트로이드 구조에 구축형 알고리즘을 적용하여 최대 가중치 합을 구하는 Pseudo Code

greedy(I, w[])
// I : 원집합 S의 부분 집합 (매트로이드)
// w[] : 가중치 배열
{
    A = empty_set();
    sort_by_weight_in_descending_order(S);
    
    for(x ∈ S)
        if(A ∪ {x}∈ I)
            A = A ∪ {x};
    
    return A;
}

 

 

 

Improvement Algorithm for Matroid Structure

- 온전한 해에서 시작하므로, 하나의 확정된 점에서 최적해에 해당하는 점을 찾아나간다.
  (즉, 공간의 한 점에서 다른 점으로 이동해간다.)
- Exchange(교환성)에서 \(A\)의 원소 하나를 제거하고, 다른 원소로 바꾸어넣는 작업이
  최적해를 찾아나가는 공간 이동의 기본 연산이다.

Example. 매트로이드 구조에 개선형 알고리즘을 적용하여 최대 가중치 합을 구하는 Pseudo Code

greedy(I, A, w[])
// I : 원집합 S의 부분 집합 (매트로이드)
// A : I의 원소
// w[] : 가중치 배열
{
    while(w(a) < w(x) && A∪{x} - {a}∈I인 a∈A와 x∈S-A가 존재)
        A = (A∪{x}) - {a};  // 공간 이동의 기본 연산
    
    return A;
}

 

 

 

Theorem. 매트로이드 \(I\) 에서 \(A \in I\) 보다 품질이 좋은 해가 존재한다면,
\(A\)와 "인접한" 해 중에서 \(A\)보다 품질이 좋은 해가 반드시 하나 이상 존재한다.
반대로, 인접한 해들 중, 보다 품질이 좋은 해가 존재하지 않는다면,
\(A\)는 Global Optimum(전역 최적해) 이다.

pf) \(A\)보다 품질이 좋은 해 \(X \in I\) 가 존재한다 가정하자.
\(X-A\) 의 원소들을 가중치가 큰 순서로 \(\{x_1, x_2, \cdots, x_k\}\),
\(A-X\) 의 원소들을 가중치가 큰 순서로 \(\{a_1, a_2, \cdots, a_k\}\) 라 하자.

\(w(A) < w(X)\) 이므로, (\(X\)가 \(A\)보다 비교적 최적해에 가까우므로)
\(w(a_i) < w(x_i)\) 인 \((a_i, x_i)\) Pair가 적어도 한 쌍 이상 존재한다.
\(i\)번째 원소에서 최초로 \(w(a_i) < w(x_i)\) 가 된다 하자.

\(X\)로부터의 Heredity(상속성)에 따라
\((A \cap X) \cup \{x_1, x_2, \cdots, x_i\} \in I\),

\(A\)로부터의 Heredity(상속성)에 따라
\((A \cap X) \cup \{a_1, a_2, \cdots, a_i\} \in I\) 이고,

\(|(A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\}| < |(A \cap X) \cup \{x_1, x_2, \cdots, x_i\}|\) 이므로,

Augmentation(증강성)에 따라,
\((A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\} \cup \{x\} \in I\) 가 되는
\(x \in \{x_1, x_2, \cdots, x_i\}\) 가 존재한다.

이렇게 만들어진 부분 집합 \((A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\} \cup \{x\} = A'\) 이라 하자.
\(|A'| \leq |A|\) 이다.

\(|A'| < |A|\) 이면,
Augmentation(증강성)에 따라 \(A - A' = \{a_i, a_{i+1}, \cdots, a_k\}\) 의 원소 중 하나를 \(A'\)에 더해서
\(A'\)를 Extension(확장)할 수 있다.

이런 식으로 \(|A'| = |A|\) 가 될 때 까지 \(A'\)를 Extension(확장)할 수 있다.
그러면 최종적으로 \(\{a_i, a_{i+1}, \cdots, a_k\}\) 중에서 한 원소 \(a\)만 빠지고, \(x\)가 들어간
\((A \cup \{x\}) - \{a\} = A'\) 가 된다.

\(w(a) \leq w(a_i) < w(x_i) \leq w(x)\) 이므로,
\(w(A) < w(A')\) 이다.
\(A'\)은 \(A\)와 원소 하나만 다른 집합이므로, \(A'\)는 \(A\)와 인접하면서 \(A\)보다 품질이 더 좋은 집합이다.

- 즉, \(A\)보다 최적해에 가까운 모든 해 \(X\)에 대해,
  \(w(A) < w(A')\) 이면서,
  \(|A'-X| = |A-X|-1\) 이 되는 \(A'\)이 존재한다는 정리이다.
  (\(A\)를 \(X\)로 한 단계 이동시켜 \(A\)보다 품질이 좋은 해를 하나 이상 찾을 수 있음을 보장할 수 있다.)
- 이것이 불가능한 해는, 자신보다 품질이 좋은 해가 없음을 의미하며, 그 자체로 전역 최적해임을 의미한다.
- 즉, 어떤 해와 인접한 더 좋은 해가 없다면, 인접 관계의 체인을 따라가며 탐색을 해봐도 더 좋은 해는 찾을 수 없다.
  (이 정리로 인해 꽤 큰 탐색 Overhead가 발생하는 일을 미연에 방지할 수 있게 되었다.)

 

 

 

Theorem. 매트로이드 \(I\)에서 서로 다른 두 전역 최적해 \(A, B \in I\)가 있다면,
이들은 원소의 집합은 다르지만, 가중치의 집합은 동일하다.

pf) 두 전역 최적해 \(A, B\)의 가중치 집합이 서로 다르다 가정하자.
\(A-B\)의 원소들을 가중치가 큰 순서대로 \(\{a_1, a_2, \cdots, a_k\}\),
\(B-A\)의 원소들을 가중치가 큰 순서대로 \(\{b_1, b_2, \cdots, b_k\}\) 라 하자.
\(i\)번째 원소에서 최초로 \(w(a_i) \neq w(b_i)\)가 된다 하자.
일반성을 잃지 않고, \(w(a_i) < w(b_i)\)라 하자.

Heredity에 따라,
\((A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\} \in I\),
\((A \cap X) \cup \{b_1, b_2, \cdots, b_i\} \in I\) 이고, 

\(|(A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\}| < |(A \cap X) \cup \{b_1, b_2, \cdots, b_i\}|\) 이므로,

Augmentation에 따라,
\((A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\} \cup \{b\} \in I\) 가 되는
\(b \in \{b_1, b_2, \cdots, b_i\}\) 가 존재한다.

이렇게 만들어진 부분 집합 \((A \cap X) \cup \{a_1, a_2, \cdots, a_{i-1}\} \cup \{b\} = A'\) 이라 하자.
\(w(a_i) < w(b_i) \leq w(b)\) 이므로,
\(w(A) < w(A')\) 이 되어,
\(A\)가 Optimum이라는 가정에 모순이 생기게 된다.

- 즉, 어떠한 서로 다른 두 최적해 \(A = \{a_1, a_2, \cdots, a_n\}\) 과 \(B = \{b_1, b_2, \cdots, b_n\}\) 에 대해서도
  가중치의 집합은 서로 같을 수 밖에 없고,
  \(w(a_j) \neq w(b_j)\) 이면서, \(w(a_i) + w(a_j) = w(b_i) + w(b_j)\) 와 같이 되면서
  품질이 같아지는 경우는 존재할 수 없음을 의미하는 정리이다.

 

 

 

Theorem. 서로 다른 어떤 두 최적해 \(A, B \in I\) 든지,
동일한 품질의 해들로 연결된 인접 관계의 체인을 따라 도달 가능하다.
즉, 매트로이드 \(I\)에서 최적해를 이루는 봉우리는 단 하나뿐이다.

pf) \(A-B\)의 원소들을 가중치가 큰 순서대로 \(\{a_1, a_2, \cdots, a_k\}\),
\(B-A\)의 원소들을 가중치가 큰 순서대로 \(\{b_1, b_2, \cdots, b_k\}\) 라 하자.

Exchange(교환성)에 따라,
\(A\)에 \(b_1\)을 더하고 \(\{a_1, a_2, \cdots, a_k\}\) 중 하나 \(a_i\)를 제거해서
\((A \cup \{b_1\}) - \{a_i\} \in I\) 를 만들 수 있다.

이 \(A \cup \{b_1\} - \{a_i\} = A'\) 라 하자.
\(w(a_i) \leq w(a_1) = w(b_1)\) 이므로,
\(w(A) \leq w(A')\) 이다.

\(A\)가 최적해이므로, \(A'\)이 \(A\)보다 좋을 수는 없어, \(w(A) = w(A')\) 이다.
즉, \(A\)는 \(b_1\)을 받아들이고, \(b_1\)과 가중치가 같은 자신의 원소 하나를 내보내는 1회 교환으로
같은 품질의 인접한 다른 최적해 \(A'\)으로 이동할 수 있다.

결과적으로, \(w(a_i) = w(a_1)\) 이다.
\(\{a_1, a_2, \cdots, a_k\}\) 에서 \(a_i\)와 \(a_1\)의 자리를 바꾸고 이름도 \(a_1, a_i\)로 바꾸어도
가중치 순서로 나열된 집합이 유지된다.
그러면, \(A' = A \cup \{b_1\} - \{a_1\}\) 로 달리 표현할 수 있다.
(즉, \(a_1\)과 \(b_1\)을 교환한 것과 같다.)

이제 \(A'-B\)의 원소들은 가중치가 큰 순서대로 \(\{a_2, \cdots, a_k\}\) 이고,
\(B-A'\)의 원소들은 가중치가 큰 순서대로 \(\{b_2, \cdots, b_k\}\) 가 된다.
앞과 같은 과정에 따라, \(A' \cup \{b_2\} - \{a_2\} \in I\)를 얻을 수 있다.
\(a_2\)는 앞에서처럼 같은 가중치의 원소와 자리와 이름을 바꾼 것일 수도 있다.
이 \(A' \cup \{b_2\} - \{a_2\}\) 를 \(A''\) 라 하자.
앞과 같은 이유로 \(w(A') = w(A'')\) 가 된다.
즉, \(A'\)은 \(b_2\)를 받아들이고, \(b_2\)와 가중치가 같은 자신의 원소 하나를 내보내는 1회 교환으로
같은 품질의 인접한 다른 최적해 \(A''\)로 이동할 수 있다.
이제 \(A'' = A \cup \{b_1, b_2\}-\{a_1, a_2\}\) 가 되었다.

위와 같은 방식으로 \(A\)로 부터 이동을 \(k\)회 수행하면 계속해서 같은 품질의 인접한 해들 \(A', A'', \cdots\) 를 거쳐
\(B\)에 이를 수 있다.
그러므로, 어떤 두 최적해든지 서로 간에 이런 이동이 가능하다.

 

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)