0
다음은 최대 2 진 정합 문제입니다. http://www.spoj.com/problems/QUEST4/ 포럼을 통해 문제를 최소 정점 커버 문제로 변환 할 수 있음을 알게되었습니다.이 문제는 최대 2 인조 매칭. 그러나 문제가 최소 꼭지점 덮개로 어떻게 변환되었는지 이해할 수 없습니다. 제발 이해 좀 도와주세요.SPOJ Quest4를 최소 정점 커버로 변환하는 방법
A
답변
1
C, R을 모든 행과 모든 열의 집합이라고합시다. G를 i 번째 행과 j 번째 열에 구멍이있는 경우 C에서 R까지의 모서리 (i, j)가있는 C와 R 사이의 모서리를 갖는 2 부분 그래프로합시다.
이제이 그래프의 정점 커버를 고려하십시오. 그래프의 정점 커버는 모든 에지가 커버되도록 노드의 최소 세트이다 (각 에지는 정점 커버의 적어도 하나의 정점에 입사한다).
문제 그래프에서 각 모서리는 구멍을 나타냅니다. 정점은 행 또는 열을 나타냅니다. 모든 에지를 덮으면서
정점을 최소화 - 동등 모든 구멍
을 덮으면서 Objective- 블록을 최소화한다.
이 질문은 프로그래밍에 관한 것이 아니기 때문에 주제가 아닌 것 같습니다. – user93353
프로그래밍에 대해 어떻게 생각하지 않습니까? 일반적으로 알고리즘에 관한 내용입니다. 그래서 프로그래밍과 관련이 있다고 생각합니다. 어쨌든,이 질문은 오랫동안 요구되었으며, 필요성은 더 이상 필요하지 않습니다. – rohitjv
규칙은 - 질문에 코드가 있고 코드에 관한 질문 인 경우 여기에 속합니다. 그렇지 않은 경우 - http://meta.stackexchange.com/questions/165519/where-should-i-post-questions -about-algorithms-stack-overflow-or-programmers-se – user93353