두 부분으로 된 그래프의 최대 매칭

Question

두 부분으로 된 그래프 문제에서 최대 매칭을 고수했습니다. 문제는 다음과 같이 나타납니다.

m 개의 원형 구멍이 있고 n 개의 원형 디스크 세트가있는 보드가 제공됩니다. 구멍은 D 1 _{같은 H 1} ..., H _미터 및 디스크로 넘버링되어 ..., N D .

m 행 n 열의 행렬 A가 있습니다. H _난 D _J를 맞출 수 있으면 A [I] [j]가 1 = (즉, H _난 ≥ D _J의 직경의 직경), 그렇지 않으면 0.

홀이 최대 하나의 디스크를 포함 할 수있는 조건이 주어지면 holedisc fitting이 최대 인 구성을 찾아야합니다.

이 문제는 네트워크 흐름 문제로 모델링 될 수 있지만 정확히 어떻게 따라갈 수는 없다는 것을 읽었습니다. 누군가 이렇게하는 방법을 설명 할 수 있습니까? 또한 볼 수있는 C 코드가 있습니까?

Answer 1

최대 흐름에 대한 이진 일치가 실제로 매우 아름답습니다. 당신이 양자 그래프를 제공하는 경우, 두 번째로 첫 번째 열에서 가장자리에 의해 연결된 노드의 두 개의 열로 그래프 생각할 수 :

A ----- 1 
    B --\ 2 
    C \- 3 
...  ... 
    Z  n 

이 최대 흐름에 문제를 줄이기 위해, 당신은 지시에 의해 시작 흐름이 왼쪽 열에서 오른쪽으로 만 이동할 수 있도록 첫 번째 열에서 두 번째 열까지 모든 모서리 이렇게 한 후에 소스 노드와 터미널 노드로 작동하는 두 개의 새 노드 s와 t를 도입합니다. 오른쪽에있는 각 노드가 연결되도록 왼쪽에있는 모든 노드와 t에 연결되도록 s를 배치합니다. 예를 들면 :

 A ----- 1 
/ B --\ 2 \ 
s- C \- 3 - t 
\ ...  .../
    Z  n 

여기 아이디어는 어떤 경로 당신이 t 왼쪽 열에서 노드 중 하나를 입력해야합니다에 다음의 걸릴 오른쪽 열에 일부 가장자리를 건너, 거기에서 T로 할 수 있다는 것입니다. 따라서 일치하는 경로와 st 경로의 가장자리에서 쉬운 일대일 매핑이 있습니다. 즉, s에서 가장자리의 소스까지 경로를 가져온 다음 가장자리를 따라 이동 한 다음 끝점에서 노드까지의 가장자리를 따라갑니다. 티. 이 시점에서, 우리의 목표는 s에서 t까지의 노드 - 비 연결 경로의 수를 최대화하는 방법을 찾는 것입니다. 우리는 다음과 같이 maximum-flow를 사용하여이를 수행 할 수 있습니다. 먼저 s를 1로 유지하면서 각 에지의 용량을 설정합니다. 이렇게하면 최대 하나의 흐름 단위가 첫 번째 열의 각 노드에 입력되도록 할 수 있습니다. 마찬가지로 두 개의 열을 교차하는 각 가장자리의 용량을 1로 설정하여 일부 다중성으로 선택하지 않고 가장자리를 선택하거나 선택하지 않습니다. 마지막으로 t에 두 번째 열을 떠나는 가장자리의 용량도 1로 설정합니다. 이렇게하면 오른쪽의 각 노드가 한 번만 일치하게됩니다. 왜냐하면 우리는 하나 이상의 흐름 단위를 밀어 낼 수 없기 때문입니다.

일단 유량 네트워크를 구축하면 표준 알고리즘을 사용하여 최대 유량을 계산하십시오. Ford-Fulkerson은 그래프에서 최대 흐름이 노드 수와 같으므로 여기서 잘 수행되는 간단한 알고리즘입니다. 최악의 경우 성능은 O (mn)입니다. 또는 고도로 최적화 된 은 O (m √ n) 시간에 훨씬 더 좋을 수 있습니다.

C 구현의 경우 Ford-Fulkerson 단계에 대한 빠른 Google 검색이 this link으로 나타났습니다. 이 코드로 전달하기 전에 흐름 네트워크를 구성해야하지만 건설이 너무 복잡하지 않아서 많은 문제가 발생하지 않아야한다고 생각합니다.

희망이 도움이됩니다.