SORT 구현을 위한 기초 이론 4 ( feat. Hungarian algorithm을 위한 이론들 )

안녕하세요. WH입니다.

오늘은 hungarian algorithm인데요

사실 바로 들어갈까하다가

hungarian algorithm을 위한 이론들을 쭉 정리하고 넘어가겠습니다

이번 글까지만 조금만 힘내봅시다

앞의 이론들 역시 같이 숙지하고 오면 좋을 것 같네요

2022.06.29 - [AI] - SORT 구현을 위한 기초 이론 2 ( feat. 베이즈 필터 )

2022.06.29 - [AI] - SORT 구현을 위한 기초 이론 3 ( feat. Kalman filter )

SORT 구현을 위한 기초 이론 2 ( feat. 베이즈 필터 )

Hall's Theorm 을 위한 기초 이론

 아니, hungarian algorithm 한다면서요? 맞아요 할껀데, 그 전에 필요한 이론이 두 개가 있어서 정리하고 가려구요. Holl's Theorm은 bipartite graph 문제에서 perfect matching에 정리인데요. 천천히 해보자구요

   Bipartite graph란

  간단히 두 개의 partition에 모든 정점이 있다고 모든 간선이 두 partition에 걸쳐 있는 graph를 생각하시면 됩니다. 음 가령 쉽게 예를 들자면, A-E 까지 한 그룹과 1-5 까지 다른 그룹이 있다고 해봅시다. 그리고 영어 그룹에 속한 정점은 같은 그룹의 정점과 이어질 수 없다고 해보죠. 즉 영어는 무조건 숫자와 이어져야해요. 이 상황을 바로 Bipartite graph 라고 하는 겁니다. 실생활 예시를 들자면 승용차 5 자리에 5명이 들어가는 자리르 선택해 앉는 상황을 생각해 볼 수 있습니다.

  Matching이란

임의의 그래프 G = ( V, E )에 대해서, 부분집합 M( E에 포함 되는 )의 모든 간선이 정점을 공유하지 않을 때, M을 matching이라고 합니다. 물론 다들 알고 계시겠지만 V는 정점, E는 간선을 의미합니다. 항상 느끼는 것이지만 정의는 왜 이렇게 어렵게 써놓는 걸까요? 모든 간선이 정점을 공유하지 않는다는 것은 그니까 정점에서 나가는 간선이 1 개라는 말입니다.

  여기서 보면, 빨간 선만을 고려한다면 정정에서 나가는 빨간선은 하나죠? 이 상황이 매칭입니다. 반대로 점선들은 고려한다면 이것은 정점에서 나가는 선이 여러개죠? 이건 matching이 아닙니다. 그럼 이쯤에서 Hell's theorm에 대해 말해봅시다. 하나의 문제 상황을 가정해보죠. 다시 자동차의 예시로 들어가겠습니다. 5개의 자리가 있고 5명의 사람이 있습니다. 5명은 각각 원하는 자리를 점선으로 나타냅니다. 문제는 이겁니다. 사람마다 원하는 자리가 다를 때, 그 사람들을 모두 원하는 자리에 앉힐 수 있을까? 사람 그룹과 자리 그룹을 나누고 원하는 자리들을 이으면 이 문제는 bipartite graph의 perfect matching 문제가 됩니다. 그럼 그런 경우의 수가 존재할까요? 이 질문에 대한 대답에 hell's theorm을 활용할 수 있습니다.

이것을 어떻게 활용하느냐. 사람을 L, 자리를 R이라고 했을 때, |S| > |N(S)| 가 되는 부분집합만 찾으면 되는 겁니다. 식이 들어가니까 무슨 말인지 어렵죠? 그럼 더 쉽게 풀어서 S는 그냥 사람을 의미하고 N(S) 는 원하는 자리를 의미합니다. 부등식을 풀어서 설명하면 5 자리를 숫자로 표현했을 때, 자리 1, 2 모두를 4 명이 원한다고 해봅시다. 그럼 자리는 2 갠데 원하는 사람은 4명이죠? 그럼 perfect matching이 존재하지 않는다는 겁니다. 쉽나요? 증명은 생략할게요. 우리는 의미만 가지고 갑시다.

Maximum Flow Problem

  뭐 이렇게 볼게 많아 이렇게 해야되? 글쎄요. 확신할 순 없지만 해서 나쁠 건 없다는 게 제 생각입니다. 언제 어디서 다시 만날지 모르니까요! maximum flow problem에서는 방향이 있는 그래프 ( directed graph ) G = ( V, E )와 함꼐 각 간선마다 용량 ( capacity ) c: E->R_+이 주어집니다. 용량은 항상 양이라고 가정해봅시다. 또한 유랑은 모두 유한하다고 해봅시다. 이렇게 주어지는 방향 그래프와 용량을 통칭하여 flow network 라고 합니다. flow network는 두 정점 s, t가 주어지는 제요 source와 sink입니다. ( 사실 t는 target의 약칭으로 많이 쓰긴하는데 여튼 sink 입니다. ) 두 정점은 항상 다른 위치에 있다고 가정해봅시다.

 

  위 상황에서 관심있는 부분은 flow입니다. s-t flow 라고도 하죠. 여튼 flow를 만족하는 함수 f : E->R_+로 정의됩니다. 또한 여기에는 두 가지 constraint가 존재합니다. capacity constraint와 flow conservatoin constriant인데요. 전자는 임의의 간선의 flow의 양은 해당 간선의 용량을 초과하지 못한다는 것을 의미하고, 후자는 source와 sink를 제외한 모든 정점에 대해 정점에서 흘러 나가는 양과 그 정점으로 흘러들어오는 양이 동일하는다는 것을 말합니다. ( 물리에서 '보존'과 관련된 정의와 비슷합니다. ) 이런 상황에서 구하고자 하는 상황은 바로 가장 큰 flow를 찾고 싶은 겁니다. 여기서 용어 하나만 정의하겠습니다. value of flow 라는 것인데요. Source에서의 flow를 말합니다. 어떻게 구해질까요? 간단합니다. 들어온 양에서 나간 양을 빼주면 됩니다. 간단하죠? 이를 수식으로 표현하면 아래와 같습니다.

위 문제를 정의할 때, 일반성을 잃지 않으면서 루프, 평행 간선, 역평행 간선이 존재하지 않는다고 말할 수 있습니다. 루프의 경우, 한 정점에서 출발해서 자기 자신으로 돌아오는 간선을 의미하기 때문에 flow와는 전혀 관련이 없죠. parallel edge란 아래의 그림으로 이해하시면 됩니다.

즉 왼쪽의 parallel edge가 존재한다면, 오른쪽의 edge로 변경하면 됩니다. 마지막으로 anti-parallel edge 입니다. 쉽게 말하면 두 정점을 순환한다고 생각하시면 됩니다. 그리고 그 graph는 정점과 간선을 추가해 줌으로서 대체할 수 있죠. 아래 그림으로 이해하시면 됩니다.

  Residual network

 이 network는 쉽게 말해서 한 번에, 최적화된 flow를 찾기 힘들기 때문에, 흐름을 수정하기 위해 정의된 network입니다. flow network G = ( V, E ), c와 flow f가 주어졌을 때, 나중에 사용할 간선들을 아래와 같이 정의합시다.

설명을 해보자면 두 개의 원소 중, 전자는 아직 흐름의 여유가 있는 간선들이며, 후자는 일정량이 흐르고 있어 흐름을 취소할 수 있는 간선들을 나타냅니다. 전자를 forward edge, 후자를 backward edge라고 합니다. E_f에 대해 orinial network와 residual network는 아래의 관계를 만족합니다.

  또한, residual network도 capacity를 정해주어야 합니다. forward edge의 경우

로 정의할 수 있습니다. 당연하죠. 생각해보면, 용량에서 현재 흐르고 있는 양을 뺀 양이 최대 용량이 될테니까요. backward edge의 경우

로 정의할 수 있겠죠. 당연히 현재 흐르고 있는 만큼만 수정할 수 있으니까요. 즉, residual network는 현재 flow를 가지고 추가로 보낼수 있고 취소할 수 있는 양들을 나타낸 network라고 할 수 있죠. 아래 예시를 보면 왼쪽은 orinal network, 오른 쪽은 그에 따른 residual network 입니다. 

   그럼 이것을 가지고 뭘할꺼냐 잔여 네트워크의 flow f_p : E_f -> R 에 대해 정의해보죠

위 식의 정의를 풀어서 설명하면 P의 간선 용량 중 가장 작은 양을 f_P라 하는 것이죠.

예를 들어 A 그림을 가지고 residual network B를 구성했다고 해봅시다. 그리고 순환이 없는 C는 B network의 P 경로라고 해봅시다. 그럼 가장 작은 flow는 2죠? f_P가 바로 2가 됩니다. 그러면 마지막으로 residual network를 이용해 기존 network의 유량을 늘리는 정의를 해보겠습니다.

  forward edge면 더해주고 backward edge면 빼줍니다. 이를 원래 network에 적용하게되면 flow 가 변하는 데요. 바로 |f| + |f_P| 만큼 변하게 됩니다. 즉 이를 정리하면 아래와 같이 됩니다.

그럼 지금까지의 내용을 Maximum flow problem에 어떻게 적용할 수 있느냐? 만약 f가 최대 흐름이라면 G_f( residual network)에서는 s에서 t로 도달할 수 없게 됩니다.

Max-flow min-cut theorem

  Net flow

  cut은 network를 두 partition으로 나누는 것을 의미합니다. 대표적으로는 source와 sink를 기준으로 나누는 방법이 있습니다. 이를 s-t cut이라고 합니다. 자 이제부터 조금 복잡해집니다. \ 는 절단을 표현합니다. 절단의 정의는 아래와 같습니다.

여기서 s는 source, t는 sink에 해당합니다. 입력으로 주어지는 flow network G= ( V, E )에 대해 어떤 cut ( S, V \ S ) 가 주어졌다고 해봅시다. S 의 정점에서 V \ S 의 한 정점으로 향하는 간선들의 집함을 아래와 같이 표현합니다.

그리고 V \ S 의 한 정점에서 S의 한 정점으로 들어오는 간선들의 집합은 다음과 같이 표시하죠

비슷하게 residual network 

에 대해서도 똑같이 적용합시다. 그럼 어떤 cut ( S , V \ S ) 에 대해 capacity는 어떻게 될까요? 델타^+의 합들 즉

속에 간선들을 더해주면 될 겁니다. 식으로 나타내면 아래와 같죠

이를 cut capacity라고 한답니다. 그럼 cut에서의 flow는 어떤가요? 아래와 같이 정의될 겁니다.

너무나도 당연한 사실이겠지만, f( S ) <= c( S ) 의 관계가 될겁니다. 물론 f ( S )는 음수가 될 수 있겠죠. 들어오는 것보다 나가는게 많을수도 있으니까요. ( 사실 이론적으로만 가능합니다. 이걸 만족하기 위해서는 sink에서도 flow의 object가 생성되어야 되죠. 뭐 여튼 ) f ( S )를 net flow value 라고 합니다. 그리고 조금만 깊게 생각해봅시다. flow의 object는 source에서만 나오고 sink에서 사라지죠. 그러면 중간에서는 어떨까요? 즉 질문은 이겁니다. cut에서는 그 flow가 어떨까 하는게 바로 질문입니다. 생성도 소멸도 이루어 지지 않고 오직 '전달'을 하는 과정 중일 겁니다. 이 말은 cut 에서의 net flow value 임의의 flow f에 대해 어떤 cut ( S, V \ S )는 항상 f( S ) = | f | 를 만족합니다.

 

  자 이제 다와갑니다. 여러 개의 cut이 있다고 해봅시다. 그럼 그 여러 개의 cut은 각각 cut capacity를 가지고 있을 겁니다. 이 중에는 min 값을 가지는 한 친구를 생각해봅시다. network 입장에서 방금 전에 언급한 min 값을 가지는 친구 보다 많은 양의 net flow를 가질 수 없게 되죠. 이는 다시 말하면, cut capcity 들 중 min 값이 source 에서 max flow를 구하는 데 영향을 미친다는 말입니다. 어떤 영향을 미칠까요? min 값과 net flow가 같다면? 즉 min 값과 | f | 가 같다면? 이것보다 큰 flow가 존재할 수 있나요? 존재할 수 없겠죠. 아 이를 조금더 정리하면 아래와 같이 되겠군요

이를 residual network와 연관하면 아래의 정리가 유도됩니다. 

위 정리의 예시는 아래 그림 예제를 통해 확인해 볼 수 있습니다.

 

즉 지금까지의 성질을 종합하면, 어떤 flow network도 max-flow의 양과 cut capacity의 양은 항상 동일하다는 사실을 이끌어 낼 수 있습니다.

Konig's Theorm

  이게 무엇이냐, 모든 bipartite graph에서 maximum matching의 크기와 minimum vertex cover의 크기는 동일하다라는 정리인데요. 바로 앞에 다룬 max-flow min-cut theorm과 비슷한 느낌이 오지 않나요? matching은 위에서 다뤘고, 이번에는 vertex cover에 대해 알아보죠. Vertex cover란 어떤 그래프 G = ( V, E )가 주어졌을 때, 부분집합 U( V에 포함되는 )에 대해, 모든 간선의 한 끝점이 U에 속하면 U를 vertex cover라 일컫는데요. 쉽게 풀어서 설명하면 정점 U와 그에 붙어 있는 간선들을 제거하면 그래프에서 아무것도 남아있지 않는 경우를 일컬어 vertex cover라 한답니다.

위 그림에서 빨간 점은 그에 붙은 선들을 제거하게 되었을 때, 모든 선이 제거 됨으로 vertex cover의 예시라고 할 수 있겠지요. Matching과 vertex cover는 다음과 같은 관계가 있습니다. 그래프 G가 주어졌을 때, M을 G의 matching, U를 G의 vertex cover라 한다면 | M | <= | U | 관계가 성립합니다. 생각해보면 당연합니다. vortex cover가 더 작다고 해봅시다. vertex cover를 빼서 matching을 없애다보면 남는 matching이 있게 됩니다. 그런데 이는 vortex cover의 정의와 맞지 않습니다. 그럼 이제 한 가지 상황을 생각해봅시다. matching과 vertex cover가 같은 경우를 생각해봅시다. vortex는 이것보다 작아질 수 있나요? 반대로 matching은 이것보다 커질 수 있을까요? 두 경우 모두 불가 합니다. 즉, 이 말을 돌려 생각해보면 matching = vertex cover라면 해당 matching과 vertex cover는 maximum matching, minimum vortex라고 할 수 있겠지요. bipartite graph 를 flow network로 만들어준다음 bipartite 에 방향을 주고 용량을 무한대로 준 이후 문제를 풀면, 유량의 값이 정수인 최대 유량을 얻을 수 잇고 그 유량 값은 maximum matching의 크기와 동일하게 됩니다. 또한 위에서 다룬 max-flow min-cut에 의해 minimum cut의 크기와도 같다는 사실을 알 수 있게 되죠.

 

많은 내용을 다뤘습니다.

사실 모든 내용을 숙지한다는 것은 쉽지가 않습니다

대략적으로라도 알고 계시길 바랍니다.

다음 글에서는 정말정말 hungarian algorithm 에 대해 다뤄보겠습니다.