원격평생교육원 이산수학 과제(그래프 문제풀이)

소개글

과제 점수 93점 받은 자료입니다.

목차

1. [문제 A] 그래프 G=(V, E)에서 V={1, 2, 3, 4}이고 E={(1,2), (2,3), (3,1), (4,1), (4,2)}일 때 그래프G를 인접행렬과 인접리스트로 나타내시오.
2. [문제 B] 다음 그래프를 깊이우선탐색 방법과 너비우선탐색 방법으로 탐색하여라. (단, a를 기준으로 탐색 하시오.)
3. [문제 C] 다음 그래프에서 오일러 순환과 해밀턴 순환이 존재하는지 판단하시오.

본문내용

[문제 A] 그래프 G=(V, E)에서 V={1, 2, 3, 4}이고 E={(1,2), (2,3), (3,1), (4,1), (4,2)}일 때 그래프G를 인접행렬과 인접리스트로 나타내시오.
인접행렬은 그래프 G=(V,E) 가 |V|=n 개의 정점을 갖는다고 하면 G 의 인접행렬은 nⅹn행렬이다. 이 인 접행렬을 A=[aij] 라고 할때 A의 각 원소 aij의 값은 다음과 같이 정의 된다.

<중 략>

즉, 정점 vi 와 정점 vj에 에지가 있으면 행렬의 해당 값을 1로, 에지가 없으면 0으로 나타낸다. 이때 두 정점 간에 중복 에지가 있을 경우 행렬 원소의 값이 1씩 증가된다.

<중 략>

인접 리스트는 그래프의 한 정점에서 연결되어 있는 정점들을 하나의 연결리스트로 표현하는 방법인데, 인접행렬의 n행들의 값을 n개의 연결 리스트로 나타내고 각 정점에 인접한 정점들을 순서와 상관없이 일일이 열거하는 것이다.

참고 자료

김대수,『이산수학 Express』, 생능출판사, 2010
박종안,『이산수학 제4판』, 경문사, 2011
박주미,『이산수학』, 한빛아카데미, 2013