2
여기에 방향 그래프 G가 있습니다. 집합이 각 꼭지점이주기에 속하는지 확인해야합니다.각 꼭지점이 하나의주기에 속하도록 각 꼭지점이 하나의주기에 속하도록 꼭지점 - 분리 사이클 세트
다항식 시간에 수행 할 수 있는지 NP-Complete로 할 수 있는지 확실하지 않습니다. 누구든지 atleast가 올바른 방향으로 나를 가리킬 수 있습니까?
A
답변
4
각 정점을 "in"정점과 "out"정점으로 분할합니다. 그런 다음 꼭지점 - 분리 순환 표지는이 그래프에서 완벽하게 일치합니다. 완벽한 매치 (즉, 다항 시간)를 찾을 수있을 때 최대한 빠르게 질문에 대한 답을 찾을 수 있습니다.
예를 들어 주시겠습니까? – bubakazouba