[자료구조] 12-1. 그래프의 기본 개념

7 bridges problem이라고도 부르는 문제다. 2개의 섬을 연결하는 7개의 다리가 있을 때 다리를 한 번씩만 건너서 돌아오는 경로를 구하는 문제다.

문제의 답을 찾지 못한 사람들이 수학자 오일러에게 이 문제를 풀도록 부탁했다. 오일러는 문제를 오른쪽처럼 단순화시켰다. 섬은 node(vertex), 다리는 edge(link)로 추상화한 것이다.

홀수 개의 엣지에 연결된 버텍스 수가 4개 이상이면 한 붓 그리기가 불가능 하므로 답은 존재하지 않는다. 하지만 이 문제를 풀기 위해 썼던 방법 즉, 그래프는 지금까지 널리 이용되고 있다.

그래프는 버텍스와 엣지의 집합이다. 어떤 개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델이다. 이를 간략히 표현하면 G=(V,E) 즉, V와 E의 집합이라고 쓴다.

또한, 버텍스는 개체, 엣지는 일대일 관계를 나타내며 버텍스와 엣지는 쌍으로 표현한다.

그래프는 이렇게 수식으로 표현한다. V는 4개의 개체를 가지고 있으며 각각의 관계(0과 2, 0과 3 등)를 맺고 있다는 표현을 E처럼 쓴다. 그림으로는 위와 같이 표현할 수 있다.

이렇게 시각적으로 표현된 그래프를 수학적으로, 또 수학적으로 표현된 수식을 그래프로 바꿀 줄 알아야 한다.

거기에 추가해 새로운 표현법이 하나 더 있다. 

- 4,4: 4개의 버텍스와 4개의 엣지를 가짐. 버텍스는 4개이므로 0부터 3까지(혹은 1부터 4까지 등등) 있다는 것을 알 수 있다.

- 0,2 / 0,3 / 1,2 / 1,3: 엣지들의 리스트를 아래에 써준다.

이렇게 엣지 리스트를 이용한 표현은 그래프를 풀어야 하는 알고리즘 코딩 문제에 많이 사용한다.

- Non-weighted, Undirected: 가장 기본적인 그래프. 개체들 사이의 관계가 대칭, 즉 0과 1이 관계를 맺으면 1과 0도 관계를 맺고 있는 형태. 모든 엣지는 평등하다.

- Non-weighted, Directed: 0과 1은 관계를 맺고 있지만 1과 0은 맺고 있지 않은 형태. 즉, 방향성을 가지고 있다. 역시 엣지는 모두 평등하다.

- Weighted, Undiredcted: 서로 가중치가 다른 관계. 엣지가 평등하지 않다.

- Weighted, Directed: 방향과 가중치가 서로 다른 관계.

예를 들어, 이 네 명이 페북 친구라고 생각해보자. 친구 관계는 서로 대칭을 이룬다. 철이가 영이의 친구면 영이도 철이의 친구인 것이다. 관계 또한 평등하다. 누가 더 친한 친구다 이런 것이 없다. 이런 관계는 개체를 버텍스로 표현하고 그 사이를 선으로 연결해준다.

만약 팔로우라고 생각해보면, 관계의 방향은 같지 않다. 관계의 평등이 깨지고 방향성이 생긴다. 따라서 버텍스를 화살표로 표현한다.

만약 서로 좋아요를 눌러주는 횟수가 다르다면? 서로의 관계에 가중치가 생긴다. 이를 가중치 그래프라고 한다.

가중치가 있으면서 방향성까지 있는 그래프도 있다.

자기 자신과 관계를 맺는 그래프는 self edge라고 한다.

버텍스가 이중으로 관계를 맺는 것은 multi edge라고 한다.

그래프는 복잡도에 따라 분류하기도 한다. 복잡도란 엣지의 수를 말한다. 버텍스의 수는 상관없다.

버텍스를 n개라고 생각해보자.

- 희소 그래프: 모든 버텍스가 상수 개의 엣지를 가지고 있다. 이 경우에는 엣지의 수가 버텍스의 수에 비례한다.

- 밀집 그래프: 거의 모든 버텍스들이 연결되어있다. 이때 엣지를 구하는 방법은 n*n이 되므로 O(n^2)가 된다.

- 완전 그래프: 모든 버텍스가 연결된 그래프이다. 엣지의 수는 nC2이므로 n(n-1)/2이다.

n개의 버텍스가 전부 서로 연결되어있는 완전 그래프는 하나의 버텍스가 가지고 있는 엣지의 수가 n-1이다. 하지만 1과 0, 0과 1의 관계가 중복되므로 2로 나눠준다. 만약 방향 그래프라면 2로 나눠줄 필요 없이 n(n-1)이 된다.

밀집 그래프는 n개의 버텍스가 대부분 서로 연결된다. 엣지는 n*n에 비례하므로 O(n^2)개라고 할 수 있다.

희소 그래프는 모든 버텍스들이 상수 k개의 버텍스와 연결된 것이다. 개수를 쓰라고 하면 k개이겠지만 이를 Big-O로 바꾸면 O(1)이라고 쓸 수 있다.