확률과 통계순열과 조합수능 기출기본 문제 (3점 중반)

수형도 차수 증명

문제

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

<증 명>
꼭짓점이 nn개 있고 차수가 1\mathrm{1}인 꼭짓점이 2\mathrm{2}개 있는 수형도 TT 를 택하자. 이때, TT의 각 꼭짓점의 차수를 d1d _{1}, d2d _{2}, ⋯\cdots, dnd _{n}이라 하자. TT의 변의 개수가 □(가)\square {( \text{가} )} 이므로 그래프의 차수의 합과 변의 개수 사이의 관계로부터 다음을 얻는다. □(나){\square {( \text{나} )}} 만약 어떤 jj에 대하여 dj≥3d _{j} \geq 3이라 가정하면 다음이 성립한다. □(다){\square {( \text{다} )}} (다)는 (나)에 모순이므로 차수가 1\mathrm{1}이 아닌 꼭짓점의 차수는 2\mathrm{2}이다.

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

(가)(나)(다)
①n−1n - 1∑i=1ndi=2n−2\displaystyle \sum\limits _{i = 1} ^{n} d _{i} = 2 n - 2∑i=1ndi≤2n−3\displaystyle \sum\limits _{i = 1} ^{n} d _{i} \leq 2 n - 3
②n−1n - 1∑i=1ndi=2n−2\displaystyle \sum\limits _{i = 1} ^{n} d _{i} = 2 n - 2∑i=1ndi≥2n−1\displaystyle \sum\limits _{i = 1} ^{n} d _{i} \geq 2 n - 1
③n−1n - 1∑i=1ndi=2n\displaystyle \sum\limits _{i = 1} ^{n} d _{i} = 2 n∑i=1ndi≥2n+1\displaystyle \sum\limits _{i = 1} ^{n} d _{i} \geq 2 n + 1
④nn∑i=1ndi=2n\displaystyle \sum\limits _{i = 1} ^{n} d _{i} = 2 n∑i=1ndi≥2n−1\displaystyle \sum\limits _{i = 1} ^{n} d _{i} \geq 2 n - 1
⑤nn∑i=1ndi=2n\displaystyle \sum\limits _{i = 1} ^{n} d _{i} = 2 n∑i=1ndi≥2n+1\displaystyle \sum\limits _{i = 1} ^{n} d _{i} \geq 2 n + 1
정답 보기
②

자료 내려받기

아직 올라온 파일이 없습니다.

해설

TT가 수형도이고 꼭짓점의 수가 nn개이므로 TT의 변의 개수는 □n−1{\square {n - 1}}이고, 그래프의 차수의 합은 변의 개수의 합의 22배이므로 □∑i=1ndi=2n−2\displaystyle {\square {\sum\limits _{i = 1} ^{n} d _{i} = 2 n - 2}}이다. 만약, 어떤 jj에 대하여 dj≥3d _{j} \geq 3이라 가정하면 □∑i=1ndi≥2n−1\displaystyle {\square {\sum\limits _{i = 1} ^{n} d _{i} \geq 2 n - 1}} (다)는 (나)에 모순이므로 차수가 11이 아닌 꼭짓점의 차수는 22이다.

태그

#이산수학#수형도#증명 빈칸

비슷한 문제 더 보기

확률과 통계 문제 모음확률과 통계 순열과 조합 문제 모음수능 문제 모음기본 문제 모음
← 전체 문제 목록으로