Vertex Cover - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:26:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:26 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#문제/알고리즘\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제/알고리즘\|알고리즘 설계와 분석]]

2025년 12월 1일 (월) 16:46에 Pinkgo님의 편집

2025-12-01T16:46:33Z

← 이전 판		2025년 12월 1일 (월) 16:46 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제/알고리즘\|알고리즘 설계와 분석]]

	==개요==		==개요==

Pinkgo: /* Vertex Cover */

2025-12-01T16:45:23Z

Vertex Cover

← 이전 판		2025년 12월 1일 (월) 16:45 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
	~~==Vertex Cover==~~
	Vertex Cover 문제는 아래와 같은 정의를 가진다.		Vertex Cover 문제는 아래와 같은 정의를 가진다.
	입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math>		입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math>

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==Vertex Cover== Vertex Cover 문제는 아래와 같은 정의를 가진다. 입력: 그래프 $G=(V,E)$ , 정수 $k$ 질문: 최대 $k$ 개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가? 해당 문제는 3-SAT <...

2025-12-01T16:45:15Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==Vertex Cover== Vertex Cover 문제는 아래와 같은 정의를 가진다. 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math> 질문: 최대 <math>k</math>개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가? 해당 문제는 3-SAT <...

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]

==개요==
==Vertex Cover==
Vertex Cover 문제는 아래와 같은 정의를 가진다.
입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math>
질문: 최대 <math>k</math>개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가?
해당 문제는 3-SAT <math> \rightarrow</math> Vertex Cover reduction을 통해서 Vertex Cover가 NP-Complete임을 보일 수 있다.
이때 Vertex Cover의 complement는 [[Independent Set]]이다.

==각주==