n 개의 노드로 구성된 무방향 그래프의 최대 간선수는? | 20년-4회차-정보처리기사-필기 기출문제 상세 페이지
120년-4회차-정보처리기사-필기
n 개의 노드로 구성된 무방향 그래프의 최대 간선수는?
1
n－1
2
n／2
3
n(n－1)／2
4
n(n＋1)
해설
n개의 정점으로 구성된 무방향 그래프에서 임의의 두 정점을 잇는 간선은 서로 다른 정점 쌍의 개수만큼 존재할 수 있으며, 이는 조합 공식 로 계산된다.
따라서 최대 간선 수는 n(n－1)／2이며, 이는 모든 정점 쌍이 서로 연결된 완전그래프의 간선 수와 같다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.