무엇을 기대했는가? 아직 지난번 포스팅을 완료하지도 않은 상태이다. 물론 배우고 서술하는게 그리 어려운 알고리즘들은 아니라고 생각되긴 하는데... 아무튼 새로운 알고리즘을 배우고 싶었기 때문에 이렇게 주제를 선정하게 되었다. 보기만 해도 웰노운의 향기가 풀풀 나지 않는가? 아무튼 나는 위의 내용들중 어떠한 것도 모르기 때문에 일단 배우러 가야할 것 같다... 여담으로 메이드 인 어비스를 봤는데 굉장히 재밌는 것 같다. 특히 어비스의 저주를 받아 고통받는 모습이 일품인 것 같다. 극장판 봐야하는데 어디서보지
1. Ear decomposition
우리는 앞서 단절점과 단절선의 정의에 대해 확인하였고, 이로부터 2-edge connectivity와 2-vertex connectivity에 대해 알아보았다. 물론 이 알고리즘들 자체만으로도 충분히 빠르지만, 그래도 일단 다른 방법을 생각해볼 수도 있다. 이런 상황에서 사용할 수 있는 알고리즘이 '귀 분할'이다. 이러한 이름은, 마치 특정한 그래프에서 이 알고리즘이 작동하는 모습이 사람의 귀를 닮았다고 해서 붙여졌다고는 하는데, 솔직히 잘 모르겠다...
귀 분할을 통해 '한번에' 해결할 수 있는 문제들은 다음과 같다: 그래프의 단절점 찾기, 그래프의 단절선 찾기, strong orientation 찾기
뭐, 일단은 설명해보도록 하겠다. 어떤 그래프에 대한 '귀 분할'이라 함은 해당 그래프의 정점들을 다음과 같은 경로들(시작점과 끝점이 같을 수도 있으며, 그 경우 사이클이 된다.) \(C_1,C_2,...,C_n \)들에 전부 포함되도록 만드는 것이다. 이때, C_1은 반드시 사이클이어야 하며, \(C_n \)의은 반드시 사이클이거나, 혹은 C_n의 양 끝점이 이전의 '귀'들에 포함되는 정점에 있어야 한다. 조금 더 직관적으로 설명하자면 대략적으로 다음과 같은 절차가 될 것이다:
처음에는 사이클을 하나 잡는 것으로 시작한다. 그 뒤, 현재까지 탐색된 정점들중 아직까지 가본적 없는 정점들을 통해 우회할 수 있는 경로를 하나 잡은 다음, 해당 경로를 새로 탐색해준다.
아 그리고 한가지 깜박한 것이 있는데, '열린 귀 분할'이라는 것은 C들중 사이클인 것이 오직 C_1밖에 없는것을 의미한다.
대충 이런 그림으로 요약할 수 있는데, chain decomposition이란 단어는 그냥 귀 분할을 의미하는 것 같다. 아무튼, 위의 그림을 통해서 우리는 귀 분할을 어떻게 찾을 것인지에 대해 생각할 수 있다. 우선, 어떤 그래프를 dfs해줄 것인데, dfs를 하는 방향과 반대 방향으로 각 간선들에 방향을 매겨준다. 조금 더 구체적으로 말하자면, G를 dfs함으로써 DFS tree가 나타날 것인데, 그곳에 속한 간선들은 아래쪽을 향하도록, 그렇지 않은 간선들은 위쪽을 향하도록 orientation을 만들어준다.
이러한 조건 하에서, 귀 분할은 어떻게 찾을 것인가? dfs를 진행한 정점들 순서대로, 다음과 같은 시행을 하면 한 개의 '귀'를 얻을 수 있다:
처음에는 어떤 아래로 내려가는 간선 하나를 잡고, 그쪽으로 이동한다. 이제 위로 올라가면서, 이미 등장한 적 있는 정점을 만난다면 그 시점에서 경로 만들기를 끝낸다.
이러한 방식을 사용하면, 일단 생각할 수 있는 것이 각 '하강 간선'들은 적어도 하나의 귀에는 포함된다는 사실이다. 왜냐하면 반드시 그쪽으로 가는걸 시도해볼 것이기 때문이다. 그리고 일부 '상승 간선'들은 어떤 귀에도 포함되지 않을 수 있다. 위의 5번 정점과 6번 정점을 잇는 간선이 분할되지 않은 것을 보면 알 수 있다. 아무튼 이런 알고리즘을 전부 거치고 나면 가능한 귀 분할을 전부 하게 된다고 한다.
그렇다면, 단절점, 단절선, strong orientation은 어떻게 구할까? 잘 생각해보면, 만약 strong orientation이 존재하는 그래프라면 우리가 간선들에 부여했던 방향이 strong orientation 그 자체임을 알 수 있다! strong orientation이 존재하는지만 판단하면 된다는 것인데, 사실 조금 더 잘 생각해보면 strong orientation이 존재하는 것은, 전체 그래프의 모든 간선을 포함하는 귀 분할이 존재함과 동치이다. 따라서 이러한 조건을 통해 확인하면 문제가 해결된다.
단절선의 경우에는 조금 더 명료하다. 귀 분할을 통해 만들어진 귀들에 들어있는 간선들은 전부 단절선일 수 없고, 그렇지 않은 간선들은 무조건 단절선이다.
단절점은 조금 귀찮은 작업이 필요하다. 일단 한가지 확실한건, 단절선에 포함된 정점들은 단절점이라는 것이다. 그 외에도, 'C_1이 아닌 사이클의 시작점(=끝점)도 단절점'인데, 그 이유는 생각을 해보다보면 직관적으로 이해할 수 있을 것이다. 물론 사이클이라면 시작점과 끝점이 다양할 수 있지 않은지 반문할 수 있겠지만, 우리의 구성방식은 항상 그 시작점과 끝점이 '맨 위'에 있도록 만듦에 유의하라.
뭐, 조금 복잡하지만 단절점과 단절선의 코드를 따로 짤 필요가 없고, strong orientation까지 한번에 처리할 수 있다는 점은 확실한 장점이다. 그 외에도, 이 아이디어를 적용하면 더욱 흥미로운 생각들을 할 수 있는데, 워낙 이 아이디어가 문제에 있어서 치명적인 스포가 될 수 있기 때문에 굳이 언급하진 않겠다.
2. Steiner tree problem
ㅁㄴㅇㄹ
3. Boruvka's algorithm
ㅁㄴㅇㄹ
4. Dominator tree
흠...방금 배우고 왔는데 굉장히 놀라운 성질이라고 생각한다. 일단, 이 알고리즘을 통해 관리하는 것은 대충 다음과 같다:
방향그래프에서, 어떤 시작점에서 다른 정점으로 이동하는데에 반드시 지나치게 되는 정점
뭐어, 일단 바로 본론으로 들어가보겠다. 일단, 어떤 방향그래프를 생각하고, 시작점 S를 생각하자. 이제 어떤 정점들 v에 대해서, 어떤 정점 u가 v의 dominator라는 것은, S에서 v로 가는 모든 경로가 u를 거침을 의미한다(즉, u를 제거하면 S에서 v로 가는 경로가 존재하지 않는다.). 근데 귀찮아서 나중에 씀
5. Erdos Gallai theorem
ㅁㄴㅇㄹ
