dtc03012   7년 전

정점이 N 개 있고 간선이 N-1 인 그래프가 있으면 그 그래프는 사이클이 없다고 단정 지을 수 있나요? ( 1 -> 1 로 가는 이런경우제외)

koosaga   7년 전

아닙니다.

4 3

1 2

2 3

3 1


정점이 N개 있고 간선이 N-1인 "연결 그래프" 는 사이클이 없다고 할 수 있습니다. (그리고 그런 그래프를 트리라고 합니다)

dtc03012   7년 전

죄송한데 예제의 간선이 N개 인거같은데요...? 제가 잘못생각하고있는건가..

koosaga   7년 전

N = 4 M = 3이라는 뜻입니다.

dtc03012   7년 전

아하 맞네요! 감사합니다 ㅎㅎㅎ 

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