교점 개수가 N인 무방향 네트워크에서 두 교점 간에 한 개의 호(Arc… | [물류관리사] 07년 1회차 기출문제 상세 페이지

교점이 n개인 무방향 네트워크에서 두 교점 간 호를 하나만 허용하면 호의 최대개수는 서로 다른 두 교점을 고르는 조합의 수, 즉 $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ 이다.
호 하나는 서로 다른 두 교점의 짝에 대응하고, 무방향이므로 순서를 구분하지 않는다. 한 교점은 자기 자신을 제외한 (n−1)개와 이어질 수 있어 총 n(n−1)가지가 나오지만, 이 방식은 같은 호를 양쪽 끝에서 한 번씩 두 번 세므로 2로 나누어 중복을 제거해야 한다.
보기의 나머지 식들은 같은 분자 n(n−1)을 3, 4, 5, 6으로 나눈 형태다. 교점 4개로 검산하면 실제 최대 호는 4·3/2 = 6개이고, 3으로 나눈 식은 4, 4로 나눈 식은 3이 되어 값이 맞지 않는다.