그래프의 임의의 한 점에서 출발하여 다른 모든 점을 한 번씩만 방문하고… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지

모든 정점을 한 번씩 방문하고 출발점으로 돌아오는 최단 경로 문제는 여행자 문제(TSP)이다.
TSP는 최소 비용 해밀턴 순환을 찾는 문제로, 대표적인 NP-하드 최적화 문제이다.
통 채우기 문제는 크기가 다른 물건을 최소 개수의 통에 담는 문제이다.
정점 커버 문제는 모든 간선의 끝점 중 하나 이상을 포함하는 최소 정점 집합을 찾는 문제이다.
그래프 색칠하기 문제는 인접한 정점이 다른 색이 되도록 최소 색 수로 칠하는 문제이다.