알고리즘 시험 준비 - [13/13 Files] - 2019-10-09

1. makeset 2. find 3. union 이렇게 3개를 가지고 union-find를 만들수 있다.

find -> level 별로 올라가니 logn union - logn 가 동일

이런 증명은 도대체 왜 하는거지 이해가 안됨 전혀

sorting -> E에 대해서 logV Sorting 한다 , MakeSet - V, Main - ElogV 각각의 edge에 대해서 logV 만큼 곱하면 된다. 

 

Def(matroid) - Let x be an infinite cost.

 

S - subsets X

 

A belong to S, we call A “independent”

 

(X, S) forms a matroid if

 

1. hereditary property: if A belongs to S, then for any subset of A, A belongs to S (유전이지 왜냐면 A1 은 A에서 나온 애니까)

2. A 랑 B랑 둘 다 S에 속하고 A보다 B가 더 크면 A에 속하지 않고 B에 속하는 x 가 있을 것이다. 그리고 그건 A 랑 X 랑 Union 해도 S에 속한다. exchange라는 게 B에 속하는 걸 A에 줘도 된다는 뜻으로 보인다. 

 

Optimization Problem 

 

Input - matroid (X, S)  where A circuit in a matroid is a minimal dependent subset of —that is, a dependent set whose proper subsets are all independent.  from wiki

 

S는 subset이고 A는 Subset인 거 같다. -> w(A)가 maximize 돼야 하는데 A의 weight를 최대화하는 것이다.

 

-----

 

X가 여기서 Vertext 로 알고 있는데

 

A <- 공집합

 

각각의 Vertex에 대해서

 

공집합이랑 x를 합친 게 S에 해당하면 

 

A <- A U x이다.

 

이렇게 하면  Time Complexity 가 엄청 높아진다. 

 

증명을 해보자 

 

A* 가 위에서 말한 optimal solution이라고 했을 때 

 

A는 greedy algorithm을 통해서 나온 Subset이라고 하자. 

 

이 2개가 같으면 되는 걸 증명하는 것이다. 

 

|A| = |A*| 

 

A의 개수가 A의 optimal 보다 맞으면 안 된다. 그냥 불가능하다고 보면 되나. 

 

반대로도 안된다. 왜 안되지.

 

뭐 그런가 보네 -> 교수님도 그냥 impossible이라고 했다.

 

그래도 둘이 같아야 x Unioin A <- S

-----

 

 

이런 케이스로 된다. 

 

----

 

여기서 말하는 forest는 cycle을 이루지 않는 tree를 뜻한다.

(X, S) - S는 subset이고 X도 Subset이다.

 

저 2개 조건 matroid 조건 위랑 똑같은데..  일단 넘어가자

 

-----

 

 

vertex 개수가 작으면 cut가 더 많다는 거네. 신기하다. 

 

---