그래프 추상화(The Graph Abstraction)

그래프는 많은 종류의 문제를 푸는데 유효한 수학적 추상화이다. 기본적으로는 그래프는 정점과 에지로부터 구성되어 에지는 두 개의 정점을 묶는다. 좀 더 정확하게는 그래프(graph)와는 묶음(V,E)로 나타내져 V는 유한 집합으로, E는V의 2항 관계이다. V는 정점 집합(vertex set)으로 불려 그 요소를 정점(vertex) 이라고 부른다. E는 에지의 집합으로 에지(edge) 와는 (u,v)의 묶음으로 u,v는V의 요소이다. 유향 그래프(directed graph)에 대해서는 에지는 순서가 있는 묶음으로 시점(source)을 종점(target)으로 접속한다.무향 그래프(undirected graph)에 대해서는 에지는 순서가 없는 묶음으로 2개의 정점을 양방향에 잇는다. 즉 무향 그래프에서는  (u,v)와(v,u)는 같은 에지의 2가지의 쓰는 법이다.

그래프의 이 정의는 몇 개의 점에서 애매 하다. 에지나 정점이 무엇을 표현 할 지가 진술되지 않았다. 그래프의 예로서는 연락 도로나 하이퍼 링크 첨부의 웹 페이지 등을 들 수가 있다. 이러한 상세가 그래프의 정의로부터는 제외되고 있는 것은 큰 이유가 있다. 그러한 자세한 것은 그래프의 추상화 중에서는 필요한 부분은 아니다. 상세를 정의로부터 제외하는 것으로 재이용 가능한 이론을 구축할 수 있어 그것은 많은 다른 종류의 문제를 풀 때에 도움이 되는 것이다.

정의에 돌아오자. 그래프는 정점과 에지의 집합이다. 실제의 모습을 보이기 위해 정점으로 문자의 라벨이 붙은 그래프를 생각해 에지를 단순하게 문자의 묶음으로 하자. 여기서 유향 그래프의 예를 다음과 같이 쓸 수가 있다.

이 그래프를 표시 하면 그림1 과 같이 된다. 에지(x,x)는 고리(self-loop)로 불린다. (b,y)와 (b,y)는 평행에지(parallel edges)이며 이것은 멀티 그래프(multigraph) 에서만 허용된다(다만 통상은 유향 그래프에서도 무향 그래프에서도 용서되지 않는다).

그림1: 유향 그래프의 예

다음에 비슷한 그래프를 나타내지만 이번은 무향 그래프이다. 이것은 그림2에 표시한다. 무향 그래프에서는 고리는 용서되지 않는다. 상기의 그래프(로부터 평행에지(b,y)를 제외한 것)의 무향판(undirected version)이다. 그것은 즉 같은 정점을 갖고 같은 에지로부터 방향을 제외한 것을 가지는 것을 의미해 (a,z)라고(z,a)말하는 2개의 에지는 하나의 에지에 퇴화 한다. 그리고 역으로 생각할 수도 있다. 무향 그래프의 유향판(directed version)은 모든 에지를 각각의 방향을 향하는 2개의 에지로 옮겨놓는 것으로 얻을 수 있다.

그림2: 무향 그래프의 예

여기서 한층 더 그래프의 용어를 정의한다. 에지(u,v)가 그래프에 포함될 때 정점v은 정점u에 도착해 인접하고 있다(adjacent)라고 말한다. 유향 그래프에서는 에지(u,v)는 정점u의 아웃에지(out-edge)이며 정점v의 인에지(in-edge)이다. 무향 그래프에서는 에지(u,v)는 정점u와v를 접합하고 있다(incident on)라고 한다.

그림1에서 정점y는 정점b에 대해서 인접하고 있다(다만b는 y에 대해서 인접하고 있지 않다). 에지(b,y)는 b의 아웃에지이며 y의 인에지이다. 그림2에서 y는b에 인접하고 있고 역도 마찬가지이다. 에지(y,b)는 정점y와 b를 접합하고 있다.

유향 그래프에 대해 어느 정점의 아웃에지의 수는 출 차수(out-degree)로 불려 인에지의 수는 입 차수(in-degree)로 불린다. 무향 그래프에 있어 어느 정점에 대해 접합하고 있는 에지의 수는 차수(degree)로 불린다. 그림1에서 정점b의 출 차수는3이며 입 차수는 0이다. 그림2에서는 단순하게 정점b의 차수는2이다.

그래프의 패스(path)이라는 것은 에지의 열로 각각의 에지의 종점이 다음의 에지의 시점인 것이다. 정점u으로부터 시작되어 정점v에서 끝나는 패스가 있다면 정점v는 u으로부터 도달 가능(reachable)이라고 한다. 패스가 단순(simple)하다는 것은 에지의 열 중에서 어느 정점도 반복해 나타나지 않는 것이다. 패스 <(b,x), (x,v)>는 단순하지만 패스<(a,z), (z,a)> 는 단순하지 않다. 그리고 패스 <(a,z), (z,a)>는 최초의 정점과 마지막 정점이 일치하므로 사이클(cycle)로 불린다. 사이클이 없는 그래프는 어사이클릭(acyclic)으로 불린다.

planar graph 란 모든 에지가 교차하지 않게 평면상에 그릴 수 있는 그래프이다. 그처럼 그려진 것은 plane graph로 불린다.  plane graph의 면(face)이란 에지에 둘러싸인 연결 성분이다.  planar graph의 중요한 특성은 면, 변, 정점의 수가 오일러의 정리：|F| - |E| + |V| = 2에 의해 관계 붙일 수 있는 것이다. 이것은 planar graph은 최대에서도O(|V|)개의 에지 밖에 가지지 않는 것을 의미한다.