① 8 ② 10 ③ 12 ④ 14 ⑤ 16
① ㄱ ② ㄴ ③ ㄱ, ㄴ
④ ㄴ, ㄷ ⑤ ㄱ, ㄴ, ㄷ
경로의 수를 구하는 문제나 행렬이 나타내는 그래프를 구할 수 있는지를 묻는 문제가 출제된다. 또, 그래프를 나타낸 행렬 의 성질을 이해하고 있는지를 묻는 문제가 출제된다.
2011년 6월 평가원
2008년 6월 평가원
01
| 출제 의도 | 그래프를 나타내는 행렬을 보고 그래프의 특징을 알 수 있는지를 묻는 문제이다.
행렬 · ‚ 이 나타내는 그래프가 될 수 있는 것만을 <보기>에서 있는 대로 고른 것은?
[3점]0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0
02
출제경향 & 대표기출문제
출제 경향
ㄱ. ㄴ. ㄷ.
보기
정답과 풀이 21쪽
01
02
03
04
꼭짓점의 집합이 {A, B, C, D, E}, 변의 집합이 {AD, AE, BD, CD, DE}인 그래프를 G라 할 때, G와 서 로 같은 그래프인 것만을 <보기>에서 있는 대로 고른 것은?
오른쪽 그래프에서 꼭짓점 A를 출발하여 한 번 지난 변을 반복하지 않고 꼭짓점 E로 이동하는 경로의 수는?
① 6 ② 7 ③ 8 ④ 9 ⑤ 10
① ㄱ ② ㄷ ③ ㄱ, ㄴ ④ ㄴ, ㄷ ⑤ ㄱ, ㄴ, ㄷ
행렬
· ‚
이 나타내는 그래프에서 한 꼭짓점에 연결된 변의 개수가 3인 꼭짓점의 개수는?① 0 ② 1 ③ 2 ④ 3 ⑤ 4
0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0
꼭짓점의 개수가 4이고 각 꼭짓점에 연결된 변의 개수가 각각 1, 2, 2, 3인 그래프를 G라 할 때, 그래프 G를 나
Level 1 기초연습
www.ebsi.co.krㄱ. ㄴ. ㄷ.
보기
A
E
C
B D
오른쪽 그래프에서 꼭짓점 A를 출발하여 한 번 지난 변을 반복하지 않고 꼭짓점 E로 이동하는 경로 중 꼭짓점 B를 지나는 경로의 수는? (단, 중간에 꼭짓점 E를 거치지 않는다.)
① 4 ② 5 ③ 6 ④ 7 ⑤ 8
오른쪽 행렬이 나타내는 그래프에서 임의의 꼭짓점에서 출발하여 모든 변을 한 번씩만 지나 출발한 꼭짓점으로 돌아오는 경로가 존재하도록 할 때, a+b의 값은?
① 0 ② 1 ③ 2 ④ 3 ⑤ 4
오른쪽 그래프를 나타내는 행렬을 P라 할 때, 행렬 P의 성분 중 0의 개수를 구하시오.
4개의 꼭짓점으로 이루어진 그래프 G에서 한 꼭짓점에 연결된 변의 개수가 최소인 꼭짓 점을 A, 한 꼭짓점에 연결된 변의 개수가 최대인 꼭짓점을 B라 하자. 그래프 G를 나타 내는 행렬 M에 대하여 행렬 M¤ 이 오른쪽과 같을 때, 그래프 G에 대한 설명 중 옳은 것만을 <보기>에서 있는 대로 고른 것은? (단, 행렬 M의 모든 성분은 0 또는 1이고, 행 렬 M의 (i, j)성분을 a‘Δ라 할 때, a¡¡=a™™=a££=a¢¢=0이다.)
① ㄱ ② ㄴ ③ ㄱ, ㄷ ④ ㄴ, ㄷ ⑤ ㄱ, ㄴ, ㄷ
01
02
04 03
정답과 풀이 22쪽
Level 2 기본연습
ㄱ. 그래프 G의 변의 개수는 4이다.
ㄴ. 꼭짓점 A를 출발하여 한 꼭짓점만을 지나 꼭짓점 B로 이동할 수 없다.
ㄷ. 두 꼭짓점 A, B는 변으로 연결되어 있다.
보기
A
E B C
D
· ‚
0 0 a 0 1 0 0 0 1 1 a 0 0 0 1 0 1 0 0 b 1 1 1 b 0
M¤ =
· ‚
1 0 1 1 0 3 1 1 1 1 2 1 1 1 1 25개의 꼭짓점 A, B, C, D, E로 이루어진 그래프 G를 나타내는 행렬이 오른쪽과 같 을 때, 그래프 G에 대한 설명 중 옳은 것만을 <보기>에서 있는 대로 고른 것은?
① ㄱ ② ㄴ ③ ㄱ, ㄷ ④ ㄴ, ㄷ ⑤ ㄱ, ㄴ, ㄷ
4개의 꼭짓점으로 이루어진 어떤 그래프를 나타내는 행렬을 M이라 할 때, 행렬 M과 행렬 M¤ 은 다음과 같다.
⋯ ⋯M=· ‚, M¤ =· ‚
행렬 M의 모든 성분의 합을 m, 행렬 M¤ 의 모든 성분의 합을 n이라 할 때, m+n의 값은?
(단, 행렬 M의 모든 성분은 0 또는 1이다.)
① 10 ② 12 ③ 14 ④ 16 ⑤ 18
1 2 2 1
0 0 0 0 0 0
01
오른쪽 그래프를 G¡, G¡에 변을 하나 추가한 그래프를 G™라 하고 G™를 나타내는 행렬을 M이라 하자. 다음 중 행렬 M¤ 의 성분 중에 0이 하나도 없도록 하기 위하 여 그래프 G¡에 추가해야 할 변은?
① AC ② AD ③ BC ④ CE ⑤ DE
02
03
정답과 풀이 23쪽
Level 3 실력완성
신유형
www.ebsi.co.kr
ㄱ. 그래프 G의 변의 개수는 6이다.
ㄴ. 꼭짓점 C는 다른 4개의 꼭짓점과 모두 변으로 연결되어 있다.
ㄷ. 꼭짓점 A를 출발하여 4개의 서로 다른 변을 지나 꼭짓점 E로 이동할 수 있다.
A B C D E
· ‚
0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0
A
B C D E
A
E
C B
D 보기