2005학년도 수능 예비평가 (이산수학) 28번

다음은 차수가 1인 꼭지점이 2개 있는 수형도에서 나머지 꼭지점의 차수는 모두 2임을 증명한 것이다.

<증명>
  꼭지점이 n개 있고 차수가 1인 꼭지점이 2개 있는 수형도 T 를 택하자. 이때, T 의 각 꼭지점의 차수를 d1, d2, …, dn이라 하자.
 T 의 변의 개수가 이므로 그래프의 차수의 합과 변의 개수 사이의 관계로부터 다음을 얻는다.
(나)
만약 어떤 j 에 대하여 dj≥3이라 가정하면 다음이 성립한다.
(다)
(다)는 (나)에 모순이므로 차수가 1이 아닌 꼭지점의 차수는 2이다.

위의 증명에서 (가), (나), (다)에 알맞은 것은? [3점]

　
  (가)      (나) (다)
① n-1 = 2n-2 ≤2n-3
② n-1 = 2n-2 ≥2n-1
③ n-1 = 2n ≥2n+1
④   n = 2n ≤2n-1
⑤   n = 2n ≥2n+1
점과 선으로만 이루어진 그래프를 수형도라고 합니다. 수형도에서꼭지점의 개수를 v, 변의 개수를 e라고 하면 v-e =1이 성립합니다.

풀이보기

(답) ②

꼭지점 v와 변 e사이의 관계는 v-e = 1이므로, 꼭지점의 개수가 n인 수형도 T 의 변의 개수는 n-1 …㉠ 입니다.

꼭지점의 차수의 합은 항상 변의 개수의 두 배이므로

d1+d2+d3+…+dn = 2(n-1) ⇔ = 2(n-1) …㉡

이 성립합니다.

차수가 1인 꼭지점이 두 개있는 수형도 T 의 꼭지점 중에서 차수가 3 이상인 꼭지점이 존재한다고 하면, 꼭지점의 차수의 합은

≥1+1+3+2(n-3) ⇔ ≥2n-1 …㉢

이 되어야 합니다. 이것은 ㉡ 에 모순이므로 차수가 3이상인 꼭지점은 존재하지 않습니다. 따라서 수형도의 차수가 1인 두 개의 꼭지점을 제외한 나머지 꼭지점의 차수는 모두 2입니다.^^

관련사항

꼭지점에 연결된 변의 개수를 꼭지점의 차수라고 합니다. 두 개의 꼭지점을 연결하여 변이 한 개 만들어지므로, 그래프에서 모든 꼭지점의 차수의 합은 항상 변의 개수의 두 배가 됩니다. ^^

목록으로

　

　

2004-01-21