[자료구조] 그래프 #1 (그래프의 정의)

오늘은 그래프 알고리즘에 대해서 알아보자.

동영상을 통하여 이야기를 할 것인데

필자의 HTML 기술 부족으로 동영상은 고정하고 글만 내리는 기능을 할 줄 모른다.

인터넷창 2개를 뛰우고 보는게 편할듯 싶다.

 

먼저 그래프에 대해서 알아보자

자료구조 시험시간이면 항상 트리와 한 묶음으로 나오는

단골 출제 문제 중 하나이다.

내가 생각하는 공부 방법은 

이게 왜 배우고 어떻게 생겼는지를 가장 먼저 이해하는 것이다.

그래야 우리가 이를 왜 배우고 왜 해야하는지를 알기에

공부의 효율도 극대가 된다. 




 먼저 그래프가 어떻게 만들어 졌는지 알아보자

먼저 세계지도가 동영상에서 나올것이다. 

우리나라 월드컵 첫을을 안겨준 유럽의 폴란드로 한번 가보자

폴란드 안에서 좀더 들어가

칼리니그라드 라는 곳에 가보자

여기에서 보이는 위성사진은 프레겔 이라는 강이다.

현재의 모습은 이렇지만



과거의 모습은  7개의 다리가 이어졌었다고 한다.

그래서 그런지 상업적으로 발달하고  경치가 좋아

많은 사람들의 관광명소가 되었다고 한다.

관광명소가되다 보니 사람들 사이에서 

" 다리를 한번씩만 건너서 모든도시를 구경할 수는 없을가 ? "



하는 궁금증이 생기고 사람들 사이에서 이 문제를 해결하려고 했다.

하지만 아무도 문제를 해결 못하고 있을때 

우리가 너무나 잘 알고 있는

레오하르트 오일러 가 말했다.

"그런 방법은 절대 존재하지 않는다."



사람들은 실망하며 그래도 찾을려고 했으나

이는 정말로 존재하지 않았다.

이 때 우리가 초등학교 때 배웠던 

연필을 뛰지 않고 한번에 그림 그리기를 생각하면 된다.

(교점이 홀수개가 0개면 아무되서나 그려도 그려지고
2개이면 홀수에서 시작하여 끝나는것 너무도 잘 알것이다.)





하지만 이게 중요한 것이 아니라 

오일러는 이를 알기 위해서

각 도시를 정점으로 잡고 이 도시를 이어주는 다리를 간선으로 잡았다.

이렇게 그리다 보니 보다 알기 쉽고 좋은 표현의 방법이 되었다.

이게 그래프의 시초가 된것이다.



그러면 그래프를 한마디로 표현하면

"정점의  모음과 이 정점을 잇는 간선의 모음 이 두 모음간의 결합"

이게 그래프 정의 이다.

보통 우리는 G = (V, E) 이렇게 표현한다.

V (Vertex) 정점의 집합.

E (Edge) 간선의 집합이다.


다음은 3가지 그래프의 종류이다.

그래프를 알기전 기본 용어를 알아야 한다.

인접, 경로, 길이, 사이클 이 있다.


인접이란 ?

 정점들이 있다. 이 정점을 있는 간선 역시도 있다.
이때 정점과 정점을 이어주는 간선이 형성되는 순간 이 두 정점을 인접한다고 한다.
쉽게 말해 연결만 되어 있으면 인접이라 한다.
(예 첫번째 그림을 보면 1 - 2 ,  2 - 3  연결된거 모두 인접이라한다.)



그럼 경로란?

연결만 하면 인접한다 했다.
이는 연결에 연결 연결에 연결도 될수 있다.
즉 둘이상의 정점의 집합이 인접을 통하여 형성되는 길(way) 이라 할수 있다.
(예 첫번째 그림을 보면 1 - 2 - 3 연결 되어 있는걸 볼수 있다. 이들 모두를 경로라 한다.)



그럼 길이는 ?

경로가 형성되었을때 이때 몇개의 간선으로 이루어 졌는가를 길이(length)라 한다.
한마디로 경로가 형성됬을때 간선의 개수 이다. 
(예  1 - 2 - 3 경로에 있어서 간선의 수가 2개이므로 길이는 2이다. )



마지막으로 싸이클?

경로가 형성되고 있을때 시작 했던 정점으로 다시 돌아 오는 경우가 생긴다.
이때를 싸이클이라 한다.
(예 1 - 2 - 3 - 1 경로에 있어서 시작 정점이 1이었으나 경로가 다시 1로 돌아 왔으니 싸이클이다. )




이제 위 첫번째 그림을 보자

이는 방향이 없어서 어느 방향으로 갈수 있다.

예를 들면 1- 2  이는

 1에서 2로 갈수 있고 2에서 1로도 갈수 있다.

이를 무방향그래프라 한다.



하지만 세번째 그림은 

화살표로 표시되어 화살표 방향으로만 가야한다.

이는 방향이 있는 방향그래프이다.



두번째 그림은 

그래프를 만들다 싸이클이 형성되지 않으면 나타나는 형태이다.

많이 봤을 것이다. 이건 트리이다. 

그래프와 트리의 차이는 싸이클의 유무 인것이다.




그래프의 기본사항에 알아 봤으니 이제 

그래프를 표현하는 방법에 대해 알아보자





그래프를 표현하는 방법으로는 크게 3가지가 있다.

그래프 그대로 표현하는  그래프 방법

행렬로 표현하는 인접행렬 방법

연결리스트로 표현하는 인접리스트 방법

이에 대해서는 자세히 설명하지 않겠다.

그림은 방향이 있던 방향이 없던 모두 표현 가능하다는 것이다.




자 이제 그래프가 어떻게 태어났는지와 

그래프의 정의와 기본적인 내용은 이제 이해를 하였다.

이제 이를 왜 배우는지 알아 볼것이다.

이는 다음 시간에 쓰도록 하겠다.






도움이 되셨다면 리플하나 남겨주세요

큰 힘이 됩니다 ^^