그래프란 무엇인가?

그래프란 무엇인가?¶

많은 사람들이 '그래프'라고 하면 데이터 세트의 표현, 즉 막대 차트나 심전도 같은 것을 연상한다. 이 장에서 다루는 그래프는 그런 것이 아니다.

이 장의 그래프는 이산의, 서로 연결된 원소들이 포함된 시스템을 모델링하기 위한 추상화라고 생각해야 한다. 여기서 원소들은 노드로 표현되고 상호 연결은 연결선으로 표현된다.

예를 들자면 도시 각각을 하나의 노드로, 도시들을 연결하는 도로를 연결선으로 표현해서 도로 지도를 그릴 수 있다. 또는 소셜 네트워크의 경우, 각 사람을 노드로 표현하고 사람들이 서로 '친구'인 경우 그들 사이에 연결선을 그리고, 그렇지 않은 경우 연결선으로 잇지 않는 식으로 표현이 가능하다.

어떤 그래프에서는 연결선들의 길이가 서로 다른데, 이것은 '가중치'나 '비용'이라고도 한다. 도로 지도에서 연결선의 길이는 두 도시 간의 거리를 나타낼 수도, 이동 시간을 나타낼 수도, 버스 요금을 나타낼 수도 있다. 소셜 네트워크에서라면 친구, 동업자 등 여러 가지 관계를 나타내기 위해 다른 종류의 연결선들이 존재할 수도 있다.

연결선은 대칭 관계를 나타낼 경우 무방향일 수도 있고, 아니면 방향을 가질수도 있다. 소셜 네트워크를 예로 들면 친구 관계는 대개 대칭이다. A라는 사람이 B와 친구라면, B는 A와 친구인 것이다. 그러니까 친구 관계는 무방향 연결선으로 표현하게 된다. 도로 지도에서라면 일방 통행인 길을 방향 연결선으로 표현한다.

그래프는 흥미로운 수학적 특성을 지니는데, 그래프 이론이라는 수학의 분파도 따로 존재한다. 그래프는 현실 문제에도 유용하게 사용되는데, 그래프 알고리즘을 사용해서 풀 수 있는 문제들이 많다. 예를 들어 다익스트라의 최단경로 알고리즘은 그래프의 특정 노드에서 다른 모든 노드에 도달하는 최단경로를 효율적으로 찾게 해주는 알고리즘이다. 경로란 연속되는 쌍들 사이에 연결선이 존재하는 일련의 노드 순서를 말한다.

굳이 찾으려 노력하지 않아도 현실의 문제와 알고리즘의 관련성이 빤히 보일 때도 꽤 있다. 도로 지도 예시에서 두 도시 간의 거리(또는 시간이나 비용)를 최소화하는 경로를 찾을 때 최단경로 알고리즘을 사용한다는 사실은 상상하기 어렵지 않다.

그러나 그래프 알고리즘을 사용해서 풀 수 있는 형식으로 문제를 표현하는 데 더 큰 노력이 드는 경우들도 있다.

방사성 붕괴 복잡계의 경우, 핵종마다 노드를 부여하고 하나의 핵종에서 다른 핵종으로 붕괴할 경우 둘 사이에 연결선을 잇는 그래프로 표현한다. 이 그래프에서 경로는 붕괴의 연쇄를 나타낸다.

두 핵종 사이의 붕괴 속도는 붕괴 상수 lamda로 표현되며 베크렐 또는 초당 붕괴 횟수로 측정한다. 여러분은 반감기인 t1/2에 더 익숙할 수도 있는데, 반감기는 표본의 절반이 붕괴되는 데 걸리는 예상 시간이다. t1/2 = ln2/lamda 관계로 양쪽 정의를 변환할 수 있다.

현재까지 가장 좋은 물리학 모델을 보면 핵 붕괴는 근본적으로 무작위한 프로세스이며, 따라서 언제 원자가 붕괴할지 예측한다는 것은 불가능하다. 하지만 lamda가 주어졌을 때 짧은 시간간격동안 하나의 원자가 붕괴할 확률 dt는 lamdadt이다.

여러 개의 붕괴 연쇄가 있는 그래프에서, 주어진 경로의 확률은 그 경로 상의 붕괴 프로세스 각각의 확률의 곱이 된다.

자, 여러분이 가장 높은 확률을 가진 붕괴 연쇄를 찾고 싶다고 하자. 각 연결선에 '길이'-log(lamda)를 부어하고 최단 경로 알고리즘을 사용하면 쉽게 찾을 수 잇다. 왜일까? 최단경로 알고리즘은 연결선들의 길이를 합하는데, 로그 확률을 더한다는 것은 확률을 곱하는 것과 동일하기 때문이다. 또한 로그에 마이너스를 붙였기 때문에 합이 최소인 것이 가장 큰 확률과 일치한다. 그래서 최단경로는 가장 일어날 확률이 높은 붕괴 연쇄가 되는 것이다.

다음은 그래프 알고리즘을 응용할 때 흔히 사용되는 유용한 프로세스다.

1. 실제 문제를 그래프 문제의 사례로 축소한다.
2. 결과를 효율적으로 계산하도록 그래프 알고리즘을 적용한다.
3. 계산 결과를 원래 문제의 해결책 관점으로 해석한다.

우리는 위 프로세스를 사용하는 다른 예시들을 곧 다시 다룰 것이다.

출처 : 위키피디아

출처 : 복잡계와 데이터 과학