정점 집합이 강하게 연결된 구성 요소의 일부인 경우 구성 요소 내의 모든 정점이 서로 도달 할 수 있다는 것을 알고 있습니다. 한주기.강력하게 연결된 구성 요소를 순환 감지로 사용
이제이 사실을 사용하여 그래프 G = (V, E)에 사이클이있는 경우 해당 사이클이 scc 내부에 있어야한다고 주장합니다.
즉, 모든주기는 scc (내 주장)의 일부 여야합니다.
내 주장에 어떤 반증을 생각할 수 없으므로 그래프에 scc의 일부가 아닌 사이클이 있는지 알고 싶습니다.
또는 내 소유권 주장이 맞습니까?
하자 전자 아니다,라고 말했다 가졌어요. 우리가 G {e}에서 v에 연결된 경우에만 인 경우이를 포함하는 G의주기입니다. 우리의 알고리즘은 단지 G {e}에서 U로부터 DFS를 실행하고, v가 u 에서 도달 가능하다면 예를 출력하고 그렇지 않으면 아니오를 출력합니다. 이 알고리즘은 DFS가 선형 시간으로 실행될 때 선형 시간으로 실행됩니다. u가 포함 된 구성 요소를 찾는 DFS 알고리즘의 일부만 실행합니다. 이 알고리즘은 분명 정확합니다. 만약 어떤 경로 p에 의해 G {e}에서 v에 연결된다면, e를 p에 추가하여 사이클을 형성 할 수 있습니다. 그렇지 않으면 G에서 e를 제거하면 u와 v가 분리됩니다.
정확합니다. 하나의 정점 세트가 하나의 싸이클에있는 경우 서로 인접하여 순환 할 수 있으므로 정의에 따라 SCC입니다.
은이 = (유, v)를 문제의 끝이 될 정확히 프로그래밍 문제 :
감사합니다. 글쎄, 나는 그것이 SCC라면 순환이라는 것을 안다. 그러나 SCC algo가 그래프 또는 일부 소수의 모든 사이클을 캡처하는지 묻습니다. 당신이 독일 셰퍼드 인 경우처럼 당신은 개입니다. 그러나 개가 그렇다면 그것은 당신이 독일 셰퍼드임을 의미하지 않습니다. 내 유추 – antz
내 대답은 정확히 말로 표현했습니다. 정점 집합이주기에 있으면 SCC에 있습니다. 네가 묻고 있었던 것이 아닌가? 어떻게 내가 그 말을 할 수 있니? – rici
아니, 네 말이 맞아. "정점 집합이주기에 있다면 SCC에 있습니다." (단수형). 그래프의 모든 사이클이 SCC인지 확인하고 싶었습니다. "정점 집합이 사이클에 있으면 SCC에 있기 때문입니다." 나는 그것이주기이지만 SCC에 의해 포착되지 않는 경우가 있을지 궁금해하고있었습니다. 당신은 아무도 없다고 말하고 있습니다. 좋아 감사합니다! 내가 필요한 것 – antz