문제 #13113

Question

30개의 교환국을 망형으로 상호 결선하려면 국간 필요한 최소 통신 회선 수는?

Accepted Answer

이 문제는 **완전 그래프(Complete Graph)**의 개념을 활용합니다. 30개의 교환국을 각각의 정점(vertex)으로 보고, 국간 통신 회선을 간선(edge)으로 생각하면, 모든 교환국이 서로 연결된 망형 구성은 모든 정점이 서로 연결된 완전 그래프가 됩니다. 완전 그래프에서 간선의 수는 $n(n-1)/2$ 공식으로 계산됩니다. 여기서 $n$은 정점의 수, 즉 교환국의 수입니다. 따라서 30개의 교환국이므로, $30 	imes (30-1) / 2 = 30 	imes 29 / 2 = 435$개의 통신 회선이 필요합니다.

문제 1