(방송통신대 이산수학 기말시험)1. 2019학년도 이산수학의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 교재 제10장의 연구과제 14번 15번 RSA 암호화와 복호화 과정에 대해

1. 2xxx학년도 『이산수학』의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 풀이를 해설하시오. 단, 문제에서 다루는 주요 용어에 대해 설명하고, 정답은 왜 정답인지, 오답은 왜 오답인지를 상세히 설명할 것. (참고: 이산수학 워크북의 해설) [30점]

1)55번 문제
다음 그래프 G와 관련된 서술 중 옳은 것은?

①G는 방향 그래프이다. ②G는 이분 그래프이다.
③G는 완전 그래프이다. ④G의 차수는 3이다.

설명
①그래프 G의 edge에 방향을 의미하는 화살표가 없으므로 방향 그래프가 아니다.
②그래프 G의 꼭지점 a, b, c를 두 개의 집합으로 분리했을 때 적어도 어느 한 집합 내부에는 edge가 존재하므로 이분 그래프가 아니다.
③그래프 G의 각 꼭지점에서의 차수(각 꼭지점에서 붙어 있는 선들의 수)는 모두 2이다.
④그래프 G에서 3개의 꼭지점 사이에 edge가 있으므로 그래프 G는 완전 그래프 K3이다.

2)56번 문제
다음 그래프 G에 관한 설명으로 부적절한 것은?

①G는 완전 그래프로서 K4 이다.
②G는 3-정규 그래프로서 큐빅 그래프라고 부른다.
③G에는 오일러 투어가 존재한다.
④G에는 해밀턴 사이클이 존재한다.

설명
…(생략)