공통수학1행렬과 그 연산수능 기출기본 문제 (3점 중반)

그래프 행렬 성분 합

문제

다섯 개의 꼭짓점 $\mathrm{A}$ , $\mathrm{B}$ , $\mathrm{C}$ , $\mathrm{D}$ , $\mathrm{E}$ 로 이루어진 그래프가 다음 조건을 만족시킨다. (가) 꼭짓점 $\mathrm{A}$ 에 연결된 변의 개수는 $4$ 이다. (나) 꼭짓점 $\mathrm{B}$ , $\mathrm{C}$ , $\mathrm{D}$ 에 연결된 변의 개수는 모두 $2$ 로 같다.

이 그래프의 각 꼭짓점 사이의 연결 관계를 나타내는 행렬의 모든 성분의 합의 최댓값을 구하시오. (단, 한 꼭짓점에서 자기 자신으로 가는 변이 없고, 두 꼭짓점 사이에 많아야 한 개의 변이 존재한다.) [3점]

정답 보기

14

자료 내려받기

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

해설

그래프에 존재하는 서로 다른 변의 개수가 최대일 때, 그래프의 각 꼭짓점 사이의 연결 관계를 나타내는 행렬의 모든 성분의 합이 최대가 된다. 조건 (가)에 의하여 꼭짓점 $\mathrm{A}$ 는 꼭짓점 $\mathrm{B}$ , $\mathrm{C}$ , $\mathrm{D}$ , $\mathrm{E}$ 와 모두 변으로 연결되어 있다. 조건 (나)를 만족하면서 서로 다른 변의 개수가 변의 개수가 최대가 되는 경우는 점 $\mathrm{B}$ 또는 $\mathrm{C}$ 또는 $\mathrm{D}$ 에 연결된 변이 모두 다른 경우로 점 $\mathrm{E}$ 가 점 $\mathrm{B}$ , $\mathrm{C}$ , $\mathrm{D}$ 와 변의로 연결되는 경우이다.

그래프의 각 꼭짓점 사이의 연결 관계를 나타내는 행렬의 모든 성분의 합은 그래프의 변의 개수의 $2$ 배이므로 구하는 최댓값은 $2 \times 7 = 14$ 이다.

← 전체 문제 목록으로

그래프 행렬 성분 합

문제

자료 내려받기

해설

태그

비슷한 문제 더 보기