레포트- 이산수학 Assignment 7

목차

1.진위 문제
2.선택 문제
3.주관식 문제

본문내용

Part 1. 진위 문제
다음 문장의 진위를 판단하고, 틀린 경우에는 그 이유를 적으시오.
2) 방향 그래프는 루프를 가질 수 있다.
- (o)
4) 오일러 그래프는 연결 그래프이다.
- (o)
6) 모든 정점이 같은 차수를 갖는 그래프를 정규 그래프라고 한다.
- (o)
8) 각 정점이 모든 다른 정점과 연결되어 있는 그래프를 완전 그래프라고 한다.
- (o)
10) 이분 그래프는 2색 가능이고, 평면상의 모든 지도는 4색으로 칠할 수 있다.
- (o)

Part 2. 선택 문제
2) 다음 그래프에서 정점 A의 차수는 얼마인가?(2)
(1) 1
(2) 2
(3) 3
(4) 4
- 정점 A는 현재 정점 B, C와 연결되어 있으므로 정점 A의 차수는 2이다.

4) 다음 그래프의 인접 형렬 표현으로 옳은 것은?(3)
(1) 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

(2) 0 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

(3) 0 1 0 0
1 0 1 0
0 1 0 1
0 0 0 1

(4) 1 0 1 1
0 1 0 1
1 0 1 0
1 1 0 1

- 그래프가 (1,2), (2,1), (2,3), (3,2), (3,4), (4,4)를 연결로 가지고 있기 때문에 답은 (3)이다.

6) 임의의 평면 그래프에서 정점의 수를 6, 연결선의 수를 9라 할 때 면의 수는 얼마인 가?(2)
(1) 4
(2) 5
(3) 6
(4) 7

- 오일러의 정리에 의해서 그래프에서 꼭지점의 수를 v, 연결선의 수를 e, 면의 수를 f라 고 할 때, v-e+f=2이다. 문제에서 정점의 수를 6, 연결선의 수를 9라 했으므로, 6-9+f=2, 즉, 면의 수 f는 5가 된다.

8) 그래프 G에 있어서 서로 다른 것은?(4)
(1) G는 이분 그래프이다.
(2) G는 2가지 색으로 칠할 수 있다.
(3) G의 모든 순환은 짝수의 길이를 가진다.
(4) G는 4가지 색으로 칠할 수 있다.

참고 자료

없음