최소 정점 덮개(그리디 vs 최적) 계산기

모든 간선의 양 끝 중 적어도 하나를 포함하는 정점 집합입니다. 교차로에 CCTV를 놓아 모든 길을 감시하거나, 테스트 케이스로 모든 상호작용을 덮는 문제가 이것입니다. 가장 작은 것을 찾는 문제는 NP-완전입니다.

아직 덮이지 않은 간선을 아무거나 하나 골라 양 끝을 둘 다 넣고, 덮인 간선을 지우기를 되풀이합니다. 이렇게 고른 간선들은 서로 끝을 나누지 않는 매칭이라 어떤 덮개든 그 개수 이상이어야 하고, 우리가 넣은 정점은 그 두 배이므로 최적의 2배를 넘지 않습니다.

대개는 더 작은 답을 내지만 보장이 없습니다. 최적의 Θ(log n)배까지 벌어지는 입력을 만들 수 있어서, 2-근사 보장선인 2배를 넘어섭니다. 이 계산기의 「그리디가 지는 입력」 예제에서는 최적 16, 2-근사 32, 그리디 34로 그리디가 2-근사에게도 집니다.

최악을 걱정해야 하면 2-근사를, 평균이 중요하면 차수 그리디를 씁니다. 「보장이 있다」와 「대개 낫다」는 다른 말입니다. 두 결과를 모두 구해 작은 쪽을 취하면 2배 보장은 그대로 유지하면서 평균도 좋아집니다.

쾨니그 정리로 최소 정점 덮개의 크기가 최대 매칭의 크기와 같아지기 때문입니다. 매칭은 다항시간에 구할 수 있으므로 이분그래프에서는 이 문제가 NP-완전이 아닙니다. 홀수 길이의 고리가 하나라도 있으면 이분그래프가 아니고 이 성질이 깨집니다.

최소 정점 덮개의 여집합이 곧 최대 독립집합입니다. 모든 간선이 덮개에 한 끝을 걸치고 있으므로, 덮개에 없는 정점끼리는 간선으로 이어질 수 없기 때문입니다. 둘을 더하면 정점 수가 됩니다.

가지치기 분기로 찾습니다. 남은 간선 중 차수가 가장 큰 정점을 골라 「넣는다」와 「넣지 않는다(그러면 이웃을 모두 넣어야 한다)」로 나눠 재귀하고, 지금까지 찾은 최선보다 커지면 그 가지를 버립니다. 정점 60개까지는 이것으로 빠르게 끝납니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.