이산수학 과제입니다.

목차

A. 그래프 G=(V,E)에서 V={1,2,3,4}이고 E={(1,2),(2,3),(3,1),(4,1),(4,2)}일때 그래프G를 인접행렬과 인접리스트로 나타내시오.
B. 다음그래프를 깊이우선탐색방법과 너비우선탐색방법으로 탐색하여라.
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) 에 에지가 있으면 행렬의 해당 값을 1로, 에지가 없으면 0으로 나타낸다.
이때 두 정점간에 중복 에지가 있을 경우 행렬 원소의 값이 1씩 증가된다. 이를 인접행렬이라하는데, 방향 없는 그래프이므로 대칭인 점 고려해서 반대칭만들면 이와 같습니다.
----1 2 3 4
1 0 1 1 1
2 1 0 1 1
3 1 1 0 0
4 1 1 0 0

참고 자료

없음