그래프 이론

위키백과 ― 우리 모두의 백과사전.

6개의 꼭지점과 7개의 변을 가지는 그래프

그래프 이론(문화어: 그라프 리론)은 그래프의 특성을 연구하는 수학의 한 분야.

그래프 이론은 전산학과도 밀접한 관계를 가지고 있다. 실생활에서 적용할 수 있는 많은 문제들은 그래프로 표시할 수 있다.

[편집] 역사

그래프 이론 최초의 연구결과로는 오일러가 1736년에 쾨니히스베르크의 다리 문제에 관해 쓴 논문이 있다. 이 논문은 그래프 이론의 초기 논문이기도 하지만 동시에 위상학의 초기 논문으로도 알려져 있다.

1845년에 구스타프 키르히호프는 전기 회로에서 전압과 전류를 계산하는데 쓰이는 키르히호프 회로 법칙을 발견하여 출판하였다.

1852년에 프란시스 구트리에는 아래와 같은 질문을 하였다.

지도를 색칠할 때 인접한 국가는 다른 색으로 칠한다고 하자. 어떠한 지도라도 4개의 색으로 칠할 수 있는가?

이 문제는 사색 문제라고 알려져 있으며 그래프 이론에 관심을 불러일으킨 계기가 된다. 이 문제를 풀기 위해 많은 그래프 이론 개념이 등장하고 이론이 발전하였다. 이 문제는 100년이 지난 후인 1976년에서야 케네스 아펠과 볼프강 하켄에 의해 풀렸다.

[편집] 그래프 자료구조

컴퓨터 시스템에 그래프를 저장하는 방법에는 여러가지가 있다. 자료구조는 그래프 구조와 그래프를 관리하는데 사용할 알고리즘에 영향을 미친다. 이론적으로 그래프는 리스트와 행렬구조중의 하나로 구별가능하다. 하지만 가장 명확하고 최적의 자료구조는 이 둘간의 조합된 형태를 띈다. 리스트 구조는 종종 sparse 그래프에 적합하며 적은 메모리 공간을 요구한다. 행렬구조는 그래프 표현에 다른 방식으로 큰 그래프의 경우 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공하는 방식이다.

[편집] 리스트 자료구조

발생 리스트(Incidence list) - 간선들은 정점들의 짝을 포함하는 배열로 표현하는 방식이다.

인접 리스트(Adjacency list) - 발생 리스트와 많은 부분 비슷하지만 각 정점이 인접한 정점들의 리스트를 가진 것을 말한다. 이 것은 방향성을 가지지 않은 그래프에서 군더더기 정보를 갖게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하지만 동시에 B의 리스트에도 A를 포함하기 때문이다. 추가적인 저장 비용이 있는 대신 인접 정보를 얻는 것은 빠르다.

[편집] 행렬 자료구조

발생 행렬(Incidence matrix) - 그래프는 간선을 행으로하고 정점을 열로하여 표현되고 [간선,정점]은 간선의 데이터를 가진다. (가장 간단한 경우: 1은 연결이고, 0은 연결되지 않은 것)

인접 행렬(Adjacency matrix) - 그래프의 정점의 개수를 행의 수와 열의 수로하는 행렬로 표현하는 것이다. 만약 정점x에서 정점y로의 간선이 존재하면 행렬성분 x행 y열의 값은 1이고 그렇지 않으면 0이다. 이 것은 부분그래프, 역그래프를 쉽게 찾게 해준다.