<div id="readability-page-1" class="page"><div id="mArticle">
				<h2 id="dkBody">티스토리 뷰</h2>
				
				<div><div data-ke-size="size16"><p><a href="https://dl.acm.org/doi/pdf/10.5555/982792.982916" target="_blank" rel="noopener&nbsp;noreferrer">https://dl.acm.org/doi/pdf/10.5555/982792.982916</a></p><p>Cut-cycle&nbsp;duality에&nbsp;의해&nbsp;$G$&nbsp;에서&nbsp;minimum&nbsp;cut을&nbsp;찾는&nbsp;것은&nbsp;$G^*$&nbsp;에서&nbsp;minimum&nbsp;cycle을&nbsp;찾는&nbsp;것과&nbsp;동일하다.&nbsp;</p><p>아이디어는,&nbsp;$G^*$&nbsp;에서&nbsp;적당한&nbsp;사이클&nbsp;$C$를&nbsp;찾은&nbsp;다음,&nbsp;$C$의&nbsp;*안*&nbsp;과&nbsp;*밖*&nbsp;에&nbsp;대해서&nbsp;분할&nbsp;정복을&nbsp;하고,&nbsp;이후&nbsp;$C$의&nbsp;안과&nbsp;밖을&nbsp;오가는&nbsp;사이클을&nbsp;찾는&nbsp;것이다.</p><p>분할&nbsp;정복이&nbsp;성립하려면&nbsp;일단&nbsp;$C$가&nbsp;$G^*$&nbsp;의&nbsp;Face들을&nbsp;공평하게&nbsp;쪼개야&nbsp;할&nbsp;것이다.&nbsp;이런&nbsp;$C$는&nbsp;$O(n)$&nbsp;시간에&nbsp;찾을&nbsp;수&nbsp;있다.&nbsp;$G^*$&nbsp;의&nbsp;모든&nbsp;Face를&nbsp;대각선에&nbsp;$\infty$&nbsp;가중치&nbsp;간선&nbsp;넣고&nbsp;대충&nbsp;triangulate하자.</p><p>다음,&nbsp;$G^*$&nbsp;에서&nbsp;아무&nbsp;정점을&nbsp;잡고,&nbsp;shortest&nbsp;path&nbsp;tree를&nbsp;만들자.&nbsp;이&nbsp;shortest&nbsp;path&nbsp;tree에는&nbsp;$\infty$&nbsp;가중치&nbsp;간선이&nbsp;전혀&nbsp;없음을&nbsp;볼&nbsp;수&nbsp;있다.&nbsp;shortest&nbsp;path&nbsp;tree를&nbsp;$T^*$&nbsp;라고&nbsp;하자.&nbsp;primal&nbsp;에서의&nbsp;$E&nbsp;\setminus&nbsp;T$는&nbsp;스패닝&nbsp;트리이며,&nbsp;dual의&nbsp;모든&nbsp;face가&nbsp;삼각형이기&nbsp;때문에&nbsp;Degree가&nbsp;3&nbsp;이하이다.&nbsp;고로&nbsp;$e$를&nbsp;제거했을&nbsp;때&nbsp;양&nbsp;컴포넌트가&nbsp;$2/3n$&nbsp;이하인&nbsp;$e$가&nbsp;존재한다.&nbsp;</p><p>이제&nbsp;다시&nbsp;dual로&nbsp;오자.&nbsp;이&nbsp;말은&nbsp;어떠한&nbsp;간선&nbsp;$e^*$가&nbsp;존재하여,&nbsp;$T^*&nbsp;+&nbsp;e^*$의&nbsp;fundamental&nbsp;cycle이&nbsp;양&nbsp;컴포넌트를&nbsp;$2/3n$&nbsp;이하로&nbsp;나눈다는&nbsp;것과&nbsp;동일하다.&nbsp;$e^*$&nbsp;가&nbsp;triangulation을&nbsp;위해&nbsp;만든&nbsp;dummy&nbsp;간선일&nbsp;수&nbsp;있는데,&nbsp;그러면&nbsp;그&nbsp;dummy&nbsp;간선이&nbsp;생긴&nbsp;face를&nbsp;기준으로&nbsp;아래쪽&nbsp;경로를&nbsp;타는&nbsp;것으로&nbsp;해&nbsp;주자.&nbsp;그러니까,&nbsp;&nbsp;$e^*$&nbsp;가&nbsp;속하는&nbsp;face가&nbsp;사이클&nbsp;안에&nbsp;들어가도록,&nbsp;그렇게&nbsp;설정해&nbsp;주면&nbsp;된다.</p></div>
<figure data-ke-mobilestyle="widthOrigin" data-filename="image.png" data-origin-width="390" data-origin-height="328"><span data-url="https://blog.kakaocdn.net/dn/co0WOp/btsALVin2WX/vLLimY0bbK0qPprHSsazV1/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/co0WOp/btsALVin2WX/vLLimY0bbK0qPprHSsazV1/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-filename="image.png" data-origin-width="390" data-origin-height="328"></span></figure>

<div data-ke-size="size16"><p>$e^*$&nbsp;가&nbsp;속하는&nbsp;face가&nbsp;$F$이고,&nbsp;$P_{ab}^*$&nbsp;이&nbsp;탄&nbsp;아래쪽&nbsp;경로이다.&nbsp;$e^*$&nbsp;가&nbsp;더미&nbsp;간선이&nbsp;아니더라도&nbsp;뭐&nbsp;이런&nbsp;식으로&nbsp;그림을&nbsp;그려줄&nbsp;수&nbsp;있겠다.</p><p>이제&nbsp;저&nbsp;사이클이&nbsp;Face를&nbsp;2/3&nbsp;크기로&nbsp;나눈다는&nbsp;것은&nbsp;알&nbsp;수&nbsp;있다.&nbsp;그러면&nbsp;재귀적으로&nbsp;저&nbsp;사이클&nbsp;안과&nbsp;밖에&nbsp;완전히&nbsp;포함되는&nbsp;최적해는&nbsp;구할&nbsp;수&nbsp;있다.<br>(dummy를&nbsp;원래&nbsp;간선으로&nbsp;바꿔주면서&nbsp;깨질&nbsp;수도&nbsp;있지&nbsp;않나요?&nbsp;-&gt;&nbsp;triangulation을&nbsp;consistent하게&nbsp;해&nbsp;준다고&nbsp;생각해&nbsp;보면&nbsp;걱정할&nbsp;필요가&nbsp;없다.)&nbsp;&nbsp;<br>(사실&nbsp;저&nbsp;사이클의&nbsp;크기가&nbsp;열라&nbsp;크면&nbsp;분할&nbsp;정복이&nbsp;깨질&nbsp;수도&nbsp;있다는&nbsp;생각은&nbsp;있다.&nbsp;degree&nbsp;2인&nbsp;정점을&nbsp;condense하는&nbsp;작업이&nbsp;필요할&nbsp;수&nbsp;있다.)</p><p>마지막으로&nbsp;저&nbsp;사이클을&nbsp;넘나드는&nbsp;경우를&nbsp;해결해야&nbsp;한다.&nbsp;$c$를&nbsp;포함하고&nbsp;사이클&nbsp;밖에&nbsp;있는&nbsp;아무&nbsp;Face를&nbsp;잡자.</p></div>
<figure data-ke-mobilestyle="widthOrigin" data-filename="image (1).png" data-origin-width="320" data-origin-height="330"><span data-url="https://blog.kakaocdn.net/dn/bmwv7M/btsAKcSt0tG/Q4fckvy9mCIbULfQS3MPz1/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/bmwv7M/btsAKcSt0tG/Q4fckvy9mCIbULfQS3MPz1/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-filename="image (1).png" data-origin-width="320" data-origin-height="330"></span></figure>

<div data-ke-size="size16"><p>넘나드는&nbsp;사이클이&nbsp;$F$와&nbsp;$F_a$&nbsp;중&nbsp;정확히&nbsp;하나만&nbsp;포함한다면,&nbsp;$s&nbsp;-&nbsp;t$&nbsp;min&nbsp;cut이고,&nbsp;$O(n&nbsp;\log&nbsp;n)$&nbsp;에&nbsp;구할&nbsp;수&nbsp;있다&nbsp;(메시라이브)</p><p>둘&nbsp;다&nbsp;포함한다고&nbsp;생각하면,&nbsp;path&nbsp;$c&nbsp;-&nbsp;a$&nbsp;안과&nbsp;밖을&nbsp;왔다&nbsp;갔다&nbsp;하거나&nbsp;$c&nbsp;-&nbsp;b$&nbsp;안과&nbsp;밖을&nbsp;왔다&nbsp;갔다&nbsp;해야&nbsp;한다.&nbsp;처음&nbsp;들어온&nbsp;순간과&nbsp;나가는&nbsp;순간을&nbsp;그냥&nbsp;shortest&nbsp;path&nbsp;$c&nbsp;-&nbsp;a$로&nbsp;대체시키면&nbsp;답이&nbsp;무조건&nbsp;그&nbsp;이상이다.&nbsp;둘&nbsp;다&nbsp;포함하지&nbsp;않는다고&nbsp;생각하면&nbsp;저&nbsp;사이를&nbsp;약간&nbsp;십자가처럼&nbsp;패싱해야&nbsp;하는데&nbsp;동일한&nbsp;논리가&nbsp;성립한다.</p></div>
<figure data-ke-mobilestyle="widthOrigin" data-filename="IMG_1191.jpg" data-origin-width="4032" data-origin-height="3024"><span data-url="https://blog.kakaocdn.net/dn/cezUdh/btsAM19YEYm/12qhIHjFUkw3s5B6TO4L2K/img.jpg" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/cezUdh/btsAM19YEYm/12qhIHjFUkw3s5B6TO4L2K/img.jpg" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-filename="IMG_1191.jpg" data-origin-width="4032" data-origin-height="3024"></span></figure>

</div>
				


				
			</div></div>

구사과

https://dl.acm.org/doi/pdf/10.5555/982792.982916
Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동일하다. 
아이디어는, $G^*$ 에서 적당한 사이클 $C$를 찾은 다음, $C$의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 $C$의 안과 밖을 오가는 사이클을 찾는 것이다.
분할 정복이 성립하려면 일단 $C$가 $G^*$ 의 Face들을 공평하게 쪼개야 할 것이다. 이런 $C$는 $O(n)$ 시간에 찾을 수 있다. $G^*$ 의 모든 Face를 대각선에 $\infty$ 가중치 간선 넣고 대충 triangulate하자.
다음, $G^*$ 에서 아무 정점을 잡고, shortest path tree를 만들자. 이 shortest path tree에는 $\infty$ 가중치 간선이 전혀 없음을 볼 수 있다. shortest path tree를 $T^*$ 라고 하자. primal 에서의 $E \setminus T$는 스패닝 트리이며, dual의 모든 face가 삼각형이기 때문에 Degree가 3 이하이다. 고로 $e$를 제거했을 때 양 컴포넌트가 $2/3n$ 이하인 $e$가 존재한다. 
이제 다시 dual로 오자. 이 말은 어떠한 간선 $e^*$가 존재하여, $T^* + e^*$의 fundamental cycle이 양 컴포넌트를 $2/3n$ 이하로 나눈다는 것과 동일하다. $e^*$ 가 triangulation을 위해 만든 dummy 간선일 수 있는데, 그러면 그 dummy 간선이 생긴 face를 기준으로 아래쪽 경로를 타는 것으로 해 주자. 그러니까,  $e^*$ 가 속하는 face가 사이클 안에 들어가도록, 그렇게 설정해 주면 된다.
$e^*$ 가 속하는 face가 $F$이고, $P_{ab}^*$ 이 탄 아래쪽 경로이다. $e^*$ 가 더미 간선이 아니더라도 뭐 이런 식으로 그림을 그려줄 수 있겠다.
이제 저 사이클이 Face를 2/3 크기로 나눈다는 것은 알 수 있다. 그러면 재귀적으로 저 사이클 안과 밖에 완전히 포함되는 최적해는 구할 수 있다.
(dummy를 원래 간선으로 바꿔주면서 깨질 수도 있지 않나요? -> triangulation을 consistent하게 해 준다고 생각해 보면 걱정할 필요가 없다.)  
(사실 저 사이클의 크기가 열라 크면 분할 정복이 깨질 수도 있다는 생각은 있다. degree 2인 정점을 condense하는 작업이 필요할 수 있다.)
마지막으로 저 사이클을 넘나드는 경우를 해결해야 한다. $c$를 포함하고 사이클 밖에 있는 아무 Face를 잡자.
넘나드는 사이클이 $F$와 $F_a$ 중 정확히 하나만 포함한다면, $s - t$ min cut이고, $O(n \log n)$ 에 구할 수 있다 (메시라이브)
둘 다 포함한다고 생각하면, path $c - a$ 안과 밖을 왔다 갔다 하거나 $c - b$ 안과 밖을 왔다 갔다 해야 한다. 처음 들어온 순간과 나가는 순간을 그냥 shortest path $c - a$로 대체시키면 답이 무조건 그 이상이다. 둘 다 포함하지 않는다고 생각하면 저 사이를 약간 십자가처럼 패싱해야 하는데 동일한 논리가 성립한다.
(두 번째 케이스의 사진)
고로 마스터 정리에 의해 전체 문제가 $O(n \log^2 n)$ 에 해결된다. $O(n \log \log n)$ 에 더 빠르게 해결할 수도 있다. https://arxiv.org/pdf/1104.4890.pdf

A deterministic near-linear time algorithm for ﬁnding minimum cuts in planar graphs

댓글