2018년 2회 정보처리기사 기출문제 15번

15. 정점이 5개인 방향 그래프가 가질 수 있는 최대 간선수는? (단, 자기간선과 중복간선은 배제한다.)

    ① 7개          ② 10개

    ❸ 20개        ④ 27개

300x250

 

이 문제는 그래프 이론 중에서 **방향 그래프(directed graph)**의 특성을 이해하고 있어야 풀 수 있습니다. 하나씩 차근차근 설명해 드릴게요.

---

✅ 문제 요약

• 정점 5개
• 방향 그래프 (간선에 방향이 있음)
• 자기 자신으로 향하는 간선(자기간선) ❌ 금지
• 중복 간선 ❌ 금지 (같은 방향 간선 중복 안 됨)

---

🔍 개념 정리: 방향 그래프에서 최대 간선 수

• **정점의 수가 nn**일 때,
• 자기간선과 중복 간선이 없으면,
• 각 정점은 나머지 n−1n - 1개 정점으로만 간선을 가질 수 있음
• 그리고 이 간선들은 방향을 가지므로, 한 방향당 1개만 가능

따라서 최대 간선 수는 다음과 같이 계산합니다:

n×(n−1)n \times (n - 1)

---

📌 정답 계산

여기서 n=5n = 5이므로:

5×(5−1)=5×4=205 \times (5 - 1) = 5 \times 4 = \boxed{20}

---

📊 보기 분석

보기 번호 간선 수 해설 정답 여부

①	7개	너무 적음	❌
②	10개	무방향 그래프 최대 간선 수 (n(n-1)/2)일 때	❌
❸	20개	✔ 정점 5개, 자기간선·중복 간선 없이 방향 고려한 최대	✅
④	27개	5개 정점이면 이 수치 불가능	❌

---

✅ 정답: ❸ 20개

---

🧠 요약 정리

그래프 종류 최대 간선 수

무방향 그래프	n(n−1)2\frac{n(n - 1)}{2}
방향 그래프	n(n−1)n(n - 1)
자기간선 허용 시	방향 그래프: n2n^2, 무방향은 변형 필요

🎓 "방향 그래프에서 자기는 제외하고 나머지 모두로 간선 가능!"