강력하게 연결된 그래프가 순환 그래프입니까, 그렇지 않은가요?

Question

저는 그래프 이론을 처음 접했을뿐만 아니라 그래프의 강력하게 연결된 구성 요소에 관해서도 매우 근본적인 의심을 가지고 있습니다. 두 노드 이상이 서로 연결되어있는 경우 두 노드 이상이 강력하게 연결되어 있다고 말합니다.이 그래프가주기가있는 순환 그래프로 적합합니까?

Answer 1

예, 강하게 연결된 그래프는 주기적입니다. 그러한 그래프에서 두 개의 꼭짓점, 예를 들어 u과 v이 강하게 연결되어 있기 때문에 u에서 v까지의 경로와 v부터 u까지의 경로가 존재합니다. u->v 경로와 v->u 경로가 연결되어 있지 않으면 연결하고주기가 있습니다. 가장자리를 공유하는 경우 u에서 시작하여 u->v 경로를 따라 가면 두 경로가 공유하는 첫 번째 경계선에 도달하면 v->u 경로를 따라 시작하여 u으로 돌아갑니다.