소프트웨어 개발정보처리기사 · 2020년09월26일 · 33/100
33.n 개의 노드로 구성된 무방향 그래프의 최대 간선수는?
1
n－1
2
n／2
3
n(n－1)／2정답
4
n(n＋1)
해설
n개의 노드를 각각 1 .. n이라 이름붙이면 1번 노드에서 모든 노드에 간선을 내면 n-1개 2번 노드는 1번노드에서 낸 것을 제외하고 n-2개 3번 노드는 1, 2번 노드에서 낸 것을 제외하고 n-3개 ... 따라서 구하는 답은 1 + 2 + ... + (n-2) + (n-1) = (n-1) * n / 2