제로웨이트 사이클 문제

Zero-weight cycle problem

컴퓨터 과학 및 그래프 이론에서, 제로 웨이트 사이클 문제는 가장자리에 가중치가 있는 유향 그래프(양수 또는 음수 또는 0일 수 있음)가 가중치의 합계가 0인 주기를 갖는지를 결정하는 문제이다.

이와 관련된 문제는 그래프에 가중치의 합계가 0보다 작은 주기가 있는지 여부를 결정하는 것입니다.이 관련 문제는 벨만-포드 알고리즘을 사용하여 다항식 시간에 해결할 수 있습니다.반면 무게 사이클이 정확히0인 것을 검출하는 것은 NP-완전한 문제입니다.[1]

사이클을 지정하면 가중치가 0임을 쉽게 확인할 수 있기 때문에 문제는 NP에 있습니다.

NP-경도의 증명은 부분집합 문제의 감소에 의한 것입니다.이 문제에서는 양의 숫자와 음의 숫자의 집합이 주어지고 합계가 정확히 0인 부분 집합이 존재하는지 여부를 결정해야 합니다.n개의 숫자를 가진 서브셋섬 인스턴스를 지정하면 다음과 같이 제로웨이트 사이클 인스턴스를 구축합니다.2n개의 꼭지점을 가진 그래프를 만듭니다.그래프에는 각 숫자에i 대해 u와i v라는 두i 개의 정점이 포함됩니다. 각i u에서 나가는 에지는 v로 가고i 가중치는i a입니다.각i v에서 n개의 나가는 가장자리가 있으며j 각 u로 가고 가중치가 0입니다.이 그래프의 모든 사이클은 u-v-u-v-1122...-u-vkk 형식을 가집니다.각 u와 대응하는i vi 사이의 모든 가중치의 합이 0인 경우, 대응하는 모든i a의 합이 0인 경우, 합이 0인 서브셋이 있는 경우, 사이클의 가중치는 0이다.

레퍼런스

  1. ^ "CMU course 15-750 — Graduate Algorithms — Spring 2010" (PDF).

외부 링크