wapas   3년 전

문제에서 "대부분의 컴퓨터 네트워크는 트리 형태로 이루어져 있다." 에서 "대부분"은 입력이 항상 트리로 온다는 보장을 하지 않습니다.

입력에서 그래프가 트리로 주어진다는 언급이 없는데 데이터는 항상 트리로 오고 있습니다.

따라서 입력 설명에서 "입력으로 주어지는 컴퓨터 네트워크는 항상 트리 형태이다." 조건이 필요합니다.

fredhur   2년 전

주어진 입력에서 노드가 N개 , 그리고 이후에 들어오는 간선의 갯수 입력이 N-1 들어온다고 하면 
문제의 입력이 트리 조건을 만족하는것이 되므로 , 입력으로 주어지는 네트워크는 모두 트리 형태라고 가정해도 괜찮지 않을까 생각합니다. 

wapas   2년 전

정점이 N개이고 간선이 N-1개인 그래프는 항상 트리가 아닙니다.

fredhur   2년 전

아 그렇군요, 자기자신으로 간다던지, 사이클이 없다는 가정도 들어가야겠군요. 좀더 엄밀하게 보는 법을 배울 수 있었습니다. 감사합니다. 

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