2020년도 1학기 이산수학 기말시험 과제물(온라인 평가)

소개글

2020년도 1학기 이산수학 기말시험 과제물(온라인 평가)

목차

1. 집합 A에서의 관계 R에 관하여 다음 물음에 답하시오. (배점: 10점)
(1) 관계 R을 방향 그래프로 나타내시오.
(2) 관계 R을 부울행렬로 나타내시오.
(3) 관계 R이 반사적인지 밝히시오.
(4) 관계 R이 대칭적인지 밝히시오.
(5) 관계 R이 추이적인지 밝히시오.

2. 그래프에 관한 다음 물음에 답하시오. (배점: 20점)
(1) K _{6}의 그래프를 그리시오.
(2) K _{6}의 그래프를 인접행렬로 나타내시오.
(3) K _{3,5}의 그래프를 그리시오.
(4) K _{4,3}의 총 차수를 구하시오.

3. 다음 그래프에 관하여 물음에 답하시오. (배점: 40점)
(1) 오일러 투어가 있는지 확인하고, 있다면 구하시오.
(2) 해밀턴 사이클이 있는지 확인하고, 있다면 구하시오.
(3) 데이크스트라 알고리즘을 이용하여 꼭지점 a에서 꼭지점 z까지의 최단경로를 구하시오. (프로그램 첨부하면 가산점 있음)

본문내용

(3) 관계 R이 반사적인지 밝히시오.
모든 a∈A에 aRa가 성립하는 경우 관계 R은 반사적. (3,3)∉A이므로, 반사적이지 않음

(4) 관계 R이 대칭적인지 밝히시오.
모든 a,b∈A에 대해서 aRb가 bRa이면 관계 R은 대칭적. (3,4)∈R이고 (4,3)∉R이므로, 관계 R은 대칭적이지 않음

참고 자료

손진곤(2013). 이산수학. 한국방송통신대학교출판문화원.