ldh5730   1년 전

각각의 노드들을 SCC로 결합하고 나서, 각각 SCC들을 각각 노드로 보았을 때 차수가 0인 SCC가 없을 수 있을까요? 

SCC들에서 차수가 0인 SCC가 없게 하려면 싸이클이 형성되기 때문에 SCC 결합할 때 이미 하나의 SCC로 묶였을 것 같은데요.

silvester71   5달 전

각각의 SCC들을 하나의 정점으로 본 그래프는 DAG(Directed Acyclic Graph)가 됩니다. 즉, 그래프에 싸이클이 있을 수 없습니다. 말씀하신대로, SCC를 하나의 정점으로 본 그래프에서 싸이클이 존재한다면 다 하나의 정점으로 묶였어야 하는데, 각각의 SCC로 남아 있기 때문에 잘못된 것입니다. 그리고 몇가지의 케이스를 직접 만들어 보시면 유향 그래프에서 진입차수가 0인 정점이 없는 경우는 사이클이 있는 경우만 성립합니다.

따라서 결론은 원래 그래프에 정점이 하나도 존재하지 않는 경우를 제외하고는 차수가 0인 SCC는 적어도 하나 존재한다는 것입니다.

댓글을 작성하려면 로그인해야 합니다.