Computer Science/Data Structures & Algorithms

[Lecture 16] Weighted Graph / 가중 그래프

Developer07 2023. 1. 15. 10:07

#Weighted Graph

수학의 그래프 이론 분야에서, 그래프 번호매김(graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다.

공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 번호매김(vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(edge-labeled graph)라고 부른다.

모서리 라벨이 순서 집합(예, 실수)의 원소라면, 이 그래프는 가중 그래프(weighted graph)라고 부른다.

이것을 특정하지 않고 쓸 경우에는, 라벨 그래프(labeled graph)는 일반적으로 모든 라벨이 다른 꼭짓점 라벨 그래프를 가리킨다. 그런 그래프는 동일하게 연속하는 정수 {1, …, |V|}로 번호매김 할 수 있으며, 이 때 |V|는 그래프의 꼭짓점의 개수이다.많은 적용에서, 모서리나 꼭짓점은 정의역과 관련이 있는 의미있는 라벨을 붙인다. 예를 들어, 모서리에 인접한 꼭짓점 사이를 이동할 때 드는 "비용"을 나타내는 가중치를 부여할 수 있다.[2]

위의 정의에서 그래프는 유한 무향 단순 그래프로 이해된다. 하지만, 번호매김의 표기는 모든 그래프의 확장과 일반화에서 적용될 수 있다. 예를 들어, 오토마타 이론과 형식 언어 이론에서 이것은 라벨 다중 그래프로 보는 것이 편리하다. 즉, 꼭짓점 쌍은 일부 라벨이 붙은 모서리로 연결될 수 있다.

 

짧게 말해 가중 그래프는 그래프 이론 용어로, 꼭짓점 / 정점과 정점 사이를 잇는 변(간선)에 가중치 / 무게 (비용)가 주어진 그래프를 말한다. 

가중 그래프 중 유향 (directed) 그래프를 네트워크(Network)라고도 한다. 각 정점들을 도시, 연결선들을 도로라고 가정하면, 가중치는 각 도로를 지나기 위한 비용이나 도시 사이의 거리라고 생각할 수 있다. 가중치는 양수와 음수 모두를 가질 수 있으며, 최단 경로 문제는 가중치의 합이 최소가 되는 경로를 구하는 문제로, 각각의 경우에 따라 문제를 해결하는 알고리즘이 서로 다르다.

[출처: Wikipedia]

 

많은 응용 프로그램에서 그래프의 각 간선에는 가중치라고 하는 관련 수치가 있다. 일반적으로 에지 가중치는 음이 아닌 정수이다. 가중 그래프는 방향이 지정되거나 방향이 지정되지 않을 수 있다.

 

간선의 무게는 종종 간선의 "비용"으로 언급된다. 응용 프로그램에서, weight는 경로의 길이, 선의 용량, 경로를 따라 위치 간 이동에 필요한 에너지 등의 척도가 될 수 있다

#다익스트라 알고리즘 / Shortest Paths (Dijkstra's Shortest Paths Algorithm)

가중 그래프와 지정된 노드 S가 주어지면, 우리는 S에서 그래프의 다른 각 정점까지의 최소 총 가중치 경로를 찾고자 한다. 경로의 총 가중치는 간선 가중치의 합이다.

 

그래프에서 DFS 또는 BFS를 수행하면 스패닝 트리가 생성되지만, 이러한 알고리즘 중 어느 것도 에지 가중치를 고려하지 않는다. 하지만 이 문제를 해결할 탐욕 (greedy)알고리즘이 바로 다익스트라 알고리즘이다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점 (Vertex)에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.

 

S를 우리가 s에서 v까지의 최단 경로 거리 D(v)를 결정한 G의 정점의 집합이라고 하자. 처음에, S = {s}와 D(s) = 0 이다. 그리고 다음을 만족하는 정점 v를 선택한다:

그런 다음 S에 v를 추가하고 D(v)를 p(v)로 설정한다. S가 s에서 도달할 수 있는 모든 정점을 포함할 때 종료한다.

#다익스트라 알고리즘의 예시

시작 정점을 a로 하자

다음은 다익스트라 알고리즘을 적용한 그래프이다

설명된 바와 같이, 알고리즘은 사용된 에지의 기록을 유지하지 않지만, 이 문제는 쉽게 해결될 수 있다. 또한 위에 도 언급했 듯이 다익스트라 알고리즘은 가중치가 음수가 아닌 그래프에만 작동한다. 하지만 negative cycle(총 무게가 음수인 주기)이 없는 경우 가중치가 음수여도 작동하는 벨먼-포드 알고리즘이 있다.

#최소 스패닝(신장) 트리 / Minimal Spanning Tree

신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다.

 

최소 비용 신장 트리는 그리디 기법을 이용하여 최적의 해를 구할 수 있으며, 대표적으로 두 가지 알고리즘, 크루스칼 알고리즘과 프림 알고리즘이 있으며, 그외 솔린 알고리즘 등이 알려져 있다.

 

림 알고리즘은 바이너리 힙을 이용하는 경우 O(|E|+|V|log|V|) 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 O(|E|log|V|), 경로 최적화를 이용하는 경우 O(|E|log∗|V|) 의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다.

 

  • 크루스칼 알고리즘 (Kruskal's algorithm) / O(E log V) 만에 최소 비용 신장트리를 구하는 알고리즘
    • 그래프의 모든 간선의 집합 E를 만든다
    • E가 비어있지 않을 때까지
      • E의 간선들 중 가중치가 최소인 간선을 지운다
      • 제된 간선이 가리키는 정점 x,y를 연결하여도 사이클이 발생하지 않는다면 연결한다.
  • 프림 알고리즘 (prim's algorithm)
    • 가중치가 있는 무방향 그래프에서 최소 비용 신장 트리 (MST, minimum spanning tree)를 구하는 그리디 알고리즘.
    • 우선순위 큐를 이용하여 구현하는 경우 O((V+E)logV)의 시간복잡도를 가진다.
    •  
    • 다익스트라 알고리즘과 거의 동일한 알고리즘이다. 다익스트라 알고리즘의 평가 함수에서 현재 경로까지의 이동거리를 누적하지 않고 간선 가중치만을 이용한다면 프림 알고리즘이 된다. 다익스트라 알고리즘과 달리 음수의 가중치가 있는 경우에도 동작 가능하다.
    • 알고리즘은 기본적으로 다음 순서로 작동한다.
      • 1. 임의의 정점을 선택하여 하나의 정점을 갖는 최초의 트리를 구성한다.
      • 2. 트리에 포함된 정점과 트리에 포함되지 않은 정점 간의 간선 중 가장 작은 가중치를 가지는 간선을 선택하여 트리에 추가한다.
      • 3. 모든 정점이 트리에 포함될 때 까지 2를 반복한다.
    • 이렇게 만들어진 트리가 최소 비용 신장 트리 문제의 최적해가 된다.

[나무위키 최소 비용 신장 트리]

#프림 알고리즘 예시

가중 그래프가 주어지면, 우리는 최소 총 가중치를 갖는 그래프에 대한 스패닝 트리를 찾고자 한다. 스패닝 트리의 총 무게는 간선의 무게의 합이다. 우리는 만약 T'가 그래프의 다른 스패닝 트리라면 T의 총 무게는 T'의 무게보다 작거나 같도록 스패닝 트리 T를 찾고 싶다고 하자.

프림 알고리즘은 앞서 봤던 다익스트라 알고리즘과 굉장히 유사하다. 프림 알고리즘은 실제로 적용되는 그래프가 연결된 경우 최소 비용의 스패닝 트리를 만든다. 위의 트리에 프림 알고리즘을 적용해보자:

#Correctness of Dijkstra’s Algorithm

S를 탐색된 노드의 집합, 즉 우리가 최종 최소 거리를 할당한 노드라고 하자. 그리고 s를 시작 정점이라고 하자.
S의 모든 꼭짓점 u에 대하여, D(u)를 s에서 u까지의 (실제) 최단 경로 거리라고 하고. S가 아닌 그래프의 모든 꼭짓점 v에 대해, p(v)를 지금까지 발견한 s에서 v까지의 최단 거리라고 하면:

Thorem: S의 각 노드 u에 대해, D(u)는 s에서 u까지의 최단 경로의 길이 이다.


이는 귀납법으로 증명 가능하다:
|S| = 1이면 {s}와 D(s) = 0이며, 이는 명백히 최소값이다.


|S| = K ≥ 1이고, 그 결과가 K에 대해 유지된다고 가정하자.


v를 S에 추가된 다음 정점으로 하고, (u,v)를 사용된 간선으로 하자. 여기서 u는 S에 있다.

 

그리고 s에서 v까지 G에 다른 경로가 있다고 가정하자.


(x,y)가 떠나는 경로의 첫 번째 간선이 되도록 하자.


그러나 D(x) + wt(x,y) ≥ D(u) + wt(u,v)이다, 그렇지 않으면 v 대신 y가 S에 추가되었을 것이다.


따라서 s에서 v까지 더 짧은 경로는 있을 수 없다.