가장자리가 남지 않을 때까지 정점 제거

Aug 16 2020

무 방향 그래프 G (V, E)가 주어지면 그래프의 Edge Set이 비워 지도록 제거 할 최소 정점 수를 찾습니다.

즉, 하나의 정점을 제거하면 해당 정점에 연결된 모든 가장자리와 함께 해당 정점을 제거합니다. 제거 후 G에 남아있는 가장자리가 없도록 제거 할 최소 정점 수를 찾습니다.

답변

3 PålGD Aug 17 2020 at 14:20

답을 직접 찾은 것처럼 들리며 Vertex Cover를 설명하는 것 같습니다 . 여러면에서 Independent Set와 매우 유사하며 두 문제 모두 NP-complete 입니다.

독립 세트와의 관계는 그래프에서 $G = (V,E)$, 세트 $S$ 최소 정점 커버입니다. $V \setminus S$ 최대 독립 세트입니다.

Independent Set가 NP-complete라는 것을 알고 있다면 Vertex Cover도 NP-complete입니다.

즉, 최대 독립 세트도 찾고 있습니다.

꼭지점 덮개 . 주어진 그래프$G = (V,E)$ 및 정수 $k$, 세트가 있습니까? $S \subseteq V$ 최대 크기 $k$ 모든 모서리가 $G$ 정점에 입사합니다. $S$?

독립 세트 . 주어진 그래프$G = (V,E)$ 및 정수 $k$, 세트가 있습니까? $S \subseteq V$ 적어도 크기 $k$되도록 유도 그래프 $G[S]$ 가장자리가 없습니까?