문제 #13465

Question

10개 국(station)을 서로 망형 통신망을 구성시 최소로 필요한 통신 회선 수는?

Accepted Answer

이 문제는 **완전 그래프**의 개념을 활용합니다. 10개의 국이 서로 망형 통신망을 구성한다는 것은 각 국이 다른 모든 국과 직접 통신할 수 있어야 함을 의미합니다. 이는 10개의 정점(국)을 가진 완전 그래프에서 모든 정점 쌍을 연결하는 변(통신 회선)의 수를 구하는 것과 같습니다. 정답은 45이며, 이는 $n$개의 정점을 가진 완전 그래프에서 필요한 변의 수는 $n(n-1)/2$ 공식으로 계산됩니다. 따라서 10개 국의 경우 $10 	imes (10-1) / 2 = 10 	imes 9 / 2 = 45$가 됩니다.

문제 1