정점이 N 개 있고 간선이 N-1 인 그래프가 있으면 그 그래프는 사이클이 없다고 단정 지을 수 있나요? ( 1 -> 1 로 가는 이런경우제외)
아닙니다.
4 3
1 2
2 3
3 1
정점이 N개 있고 간선이 N-1인 "연결 그래프" 는 사이클이 없다고 할 수 있습니다. (그리고 그런 그래프를 트리라고 합니다)
죄송한데 예제의 간선이 N개 인거같은데요...? 제가 잘못생각하고있는건가..
N = 4 M = 3이라는 뜻입니다.
아하 맞네요! 감사합니다 ㅎㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
dtc03012 7년 전
정점이 N 개 있고 간선이 N-1 인 그래프가 있으면 그 그래프는 사이클이 없다고 단정 지을 수 있나요? ( 1 -> 1 로 가는 이런경우제외)