지난 글 : [알고리즘] - 이진 탐색
이산수학에서의 그래프
'그래프(graph)'라 하면 원 그래프나 막대 그래프 등을 떠올린다.하지만 컴퓨터 과학이나 이산수학에서 사용되는 '그래프'는 뉴런처럼 '정점(혹은 노드(node))'이라는 것과 정점과 정점을 연결하는 선, '간선(혹은 링크(link))'으로 이루어져있다. 즉, 그래프는 몇 개의 정점이 간선으로 연결된 것을 가리킨다.
그래프는 다양한 것들을 표현할 수 있다
그래프는 세상에 존재하는 다양한 것들을 표현할 수 있어 편리하다. 예로 역을 정점으로 하고 경로상 인접한 두 역을 선으로 연결하면 노선도를 나타내는 그래프가 만들어진다. 또, 컴퓨터 네트워크에서 라우터(router)를 정점으로 하고 링크로 연결된 두 개의 라우터를 간선으로 이으면 네트워크 접속 관계를 나타내는 그래프가 만들어진다고 한다.
가중 그래프
위에서 본 그래프는 정점과 간선으로만 이루어졌지만, 간선에 가중치를 부여한 그래프도 있다 한다.
간선에 부여된 값을 간선의 '가중치'또는 '코스트(cost)'라 하며 이런 그래프를 '가중 그래프(weighted graph)'라 한다. 간선에 가중치가 없을 때는 두 개의 정점은 '연결돼 있거나', '연결돼 있지 않거나' 둘 중 하나지만, 가중치가 있을 때는 '연결(관계)의 정도'를 표현할 수 있다. 예로 노선도 그래프에서 열차가 두 개의 역을 이동할 때 걸리는 시간을 간선의 가중치로 하면 이동 시간을 나타내는 그래프가 된다. 혹은 두 역 간의 운임을 간선의 가중치로 하면 이동에 걸리는 운임을 나타내는 그래프를 얻을 수 있다. 정점에도 가중치가 붙는 경우가 있지만 서적에서는 다루지 않는다.
방향성 그래프
예로, 노선도 등에서 일방통행만 가능하다는 것을 나타내고 싶을 때 간선에 방향을 부여할 수도 있다 한다. 이런 그래프를 '방향성 그래프(directed graph)'라 한다. 이와 반대로, 간선에 방향이 없는 경우를 '비방향성 그래프(undirected graph)'라고 한다. 방향성 그래프에도 비방향성 그래프처럼 간선에 가중치를 부여할 수 있다. 방향성 그래프를 통해 비대칭인 가중치도 표현할 수 있다.
그래프 사용시 편리점
그래프를 사용하면 무엇이 좋을까? 예로 그래프상에 지정한 두 정점 s와 t를 연결하는 간선들 중 s에서 출발해 t에 도착할 때까지 가중치의 합이 가장 작은 경로를 찾는 알고리즘이 있다 해보자. 이 알고리즘은 컴퓨터 네트워크상에서 통신 시간이 가장 짧은 경로를 찾거나 노선도에서 이동 시간이 가장 짧거나 운임이 가장 싼 경로를 찾을 때 등 다양한 곳에 적용할 수 있다. 이처럼 다양한 대상을 그래프라는 하나의 도구로 나타내므로 그래프상의 문제를 해결하는 알고리즘을 찾을 수 있고, 이 알고리즘을 형태가 다른 다양한 문제에 적용할 수 있다.
앞으로 책을 통해 그래프 탐색 및 최단 경로 문제 등 그래프상의 기본적인 문제에 대한 알고리즘을 배운다. 그래프 탐색이란 특정 정점에서 출발해 간선을 통해 이동하며 대상 정점을 찾는 것이다. 탐색 순서에 따라 '너비 우선 탐색'과 '깊이 우선 탐색' 두 종류가 있다. 최단 경로 문제는 위에 든 예처럼 지정한 두 정점 s와 t를 연결하는 경로 중 간선의 가중치 합이 가장 작은 것을 찾는 문제이다.
참고 서적 :
