이것은 알고리즘 설계 관련 문제입니다.O (n^2) 시간을 사용하여 이진 일치에서 실수를 수정하십시오.
V = (A, B) 인 정점 G = (V, E)를 갖는 2 부분 그래프가 주어진다면, | A | = | B | = n.
우리는 B의 A에서 n-2 노드의 n-2 노드를 완벽하게 일치시킵니다. 그러나 A의 나머지 두 노드의 경우 두 노드를 모두 B의 특정 노드에 매핑합니다 (n-2
위의 "일치"의 정보가 주어지면 A와 B 사이의 완벽한 일치가 실제로 존재하는지 여부를 결정하기 위해 O (n^2) 시간을 사용하는 방법은 무엇입니까? 힌트가 좋다. 고맙습니다.
u와 v가 B의 동일한 노드 x와 일치하는 A의 두 노드가되도록합시다. 두 노드 중 하나를 선택하여 u라고 부르고 일치하는 부분에서 x로 가장자리를 제거하십시오. 이제 A에서 노드의 n-1과 B에서 노드의 n-1 사이의 일치가있는 그래프가 남았습니다. 문제는 더 큰 것으로 만들기 위해이 일치를 확장 할 수 있는지 여부입니다.
Berge 's theorem을 사용하여이 작업을 수행하는 정말 좋은 방법은 두 개의 불일치하는 노드 사이에 경로가없는 경우에만 그래프에서 일치가 최대라는 것입니다. 교차 경로는 일치 항목에 포함되지 않은 모서리와 일치 항목에 포함 된 모서리를 번갈아 사용하는 것입니다. 노드 u에서 시작하여 수정 된 2 진 검색을 수행하여 x에 대한 경로를 찾으려고하면 A와 B 사이에서 우연히 일치하지 않는 가장자리를 따라갈 수 있고 B에서 A로 이동하면 x와 같은 경로를 찾을 수 있습니다. 당신은 단지 일치하는 가장자리를 따릅니다. u에서 x까지 번갈아 가며있는 경로가 있다면,이 방법을 찾아야합니다. 그런 경로가 없다면 그 경로도 확실 할 것입니다.
u에서 x까지의 경로가 교차하는 경우 "뒤집어서"일치하는 크기를 1 씩 늘릴 수 있습니다. 특히, 일치하는 경로에없는 모든 가장자리를 가져 와서 추가하고 일치하는 모든 가장자리를 가져 와서 삭제하십시오. 결과는 당신이 시작한 것보다 한가지 더 많은 모서리가있는 유효한 매칭입니다. (이것이 왜 보이지 않거나, 몇 가지 예를 가지고 놀고, 찾은 것을 보거나, Berge의 정리의 증거를보세요.) .
전반적으로,이 접근법은 시간 O (m + n)을 필요로하며, 여기서 m은 그래프의 가장자리 수이고 n은 노드 수입니다. 가장자리 m의 수는 bipartite 그래프에서 O (n) 이하이므로 시간 경계에 일치합니다. 실제로는 실제로는 더 단단합니다.
이 문제를 최대 흐름으로 변환하십시오 min 커트 문제는 유닛 용량 에지에 의해 A에 접속 된 소스 s 및 유닛 용량 에지에 의해 B가 접속되는 싱크 t를 부가함으로써 발생한다.
templatypypedef가 대답 한 바에 따르면이 네트워크에서 이미 크기 n-1의 흐름이 있습니다.
이제 플로우의 크기를 n으로 늘릴 수 있는지 여부를 결정하는 것이 문제입니다. 이것은 O (E) = O (n^2) 시간이 걸리는 Edmonds-Karp 발견법의 한 라운드를 실행함으로써 달성 될 수 있습니다 (즉, 위의 크기 n-1의 흐름의 나머지 그래프에서 최단 경로를 찾고 병목 현상).
대단히 고마워요! 방금이 문제를 내 대답의 네트워크 흐름 문제로 바꿨습니다 (이 문제는 책의 네트워크 흐름 섹션에서 가져온 것입니다). – HLC