Vertex Cover: 두 판 사이의 차이
youngwiki
새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==Vertex Cover== Vertex Cover 문제는 아래와 같은 정의를 가진다. 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math> 질문: 최대 <math>k</math>개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가? 해당 문제는 3-SAT <... |
편집 요약 없음 |
||
| (같은 사용자의 중간 판 하나는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
[[분류:알고리즘 설계와 분석]] | [[분류:알고리즘 설계와 분석]] | ||
[[분류:컴퓨터 공학]] | [[분류:컴퓨터 공학]] | ||
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] | 상위 문서: [[알고리즘 설계와 분석#문제/알고리즘|알고리즘 설계와 분석]] | ||
==개요== | ==개요== | ||
Vertex Cover 문제는 아래와 같은 정의를 가진다. | Vertex Cover 문제는 아래와 같은 정의를 가진다. | ||
입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math> | 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math> | ||
2025년 12월 1일 (월) 16:46 기준 최신판
상위 문서: 알고리즘 설계와 분석
개요
Vertex Cover 문제는 아래와 같은 정의를 가진다.
입력: 그래프 , 정수 질문: 최대 개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가?
해당 문제는 3-SAT Vertex Cover reduction을 통해서 Vertex Cover가 NP-Complete임을 보일 수 있다. 이때 Vertex Cover의 complement는 Independent Set이다.
