그래프 이론

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭지점과 7개의 변을 가지는 그래프

그래프 이론(문화어: 그라프 리론)은 그래프의 특성을 연구하는 수학컴퓨터 과학의 한 분야로, 특정 집단내 대상들 간의 관계를 그래프로 나타낸 수학적 구조이다. 여기서의 그래프노드(nodes)와 두 노드를 연결하는 선(edge)으로 구성되어 있다. 이러한 그래프 가운데 방향이 없는(undirected) 그래프는 노드들 간에 차이가 없음을 의미하며, 방향이 있는(directed) 그래프 역시 존재한다. 그래프 이론에서의 그래프와 다른 일반 수학적인 그래프와 혼동하지 말아야 한다.


역사[편집]

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

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

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

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

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

그래프 자료구조[편집]

컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 자료 구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다. 이론적으로 그래프는 리스트행렬구조중의 하나로 구별가능하다. 하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤다. 리스트 구조는 종종 sparse graphs에 적합하며 적은 메모리 공간을 요구한다. 행렬구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공한다.

리스트 자료구조(List Structures)[편집]

발생 리스트(Incidence list) - 선들은 선으로 연결된 두 노드(방향이 있다면 순서가 존재함)와 가중치(weight), 다른 특정 데이터들을 포함하는 배열로 표현된다. 선으로 연결된 두 노드는 서로 인접(adjacent)한 관계라고 일컫는다.

인접 리스트(Adjacency list) - 발생 리스트와 비슷하게도, 각 꼭지점이 인접한 꼭지점들의 리스트를 가진다. 따라서 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하게 되며 동시에 B의 리스트에도 A가 포함된다. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라진다.

행렬 자료구조(Matrix Structures)[편집]

발생 행렬(Incidence matrix) - 그래프는 변(edge)을 열로하고 꼭지점(vertex)을 행으로하는 행렬로 표현되며, 행렬 [꼭지점,변]은 변의 끝점에 대한 데이터를 가진다(가장 간단한 경우: 1은 연결됨을 의미, 0은 연결되지 않음을 의미). 행렬의 크기는 |V|\cdot |E| (꼭지점의 수 \times 변의 수)로 나타낸다.

인접 행렬(Adjacency matrix) - 인접 행렬의 크기는 |V|\cdot |V| (꼭지점의 수)로 나타낸다. 만약 꼭지점x에서 꼭지점y로 변이 존재하면 행렬성분 x행 y열의 값은 1이고 그렇지 않으면 0이다. 이것은 부분그래프(subgraph), 역(reverse)그래프를 쉽게 찾게 해준다.

키르히호프 행렬(Kirchhoff matrix)-

거리 행렬(Distance matrix)-

그래프 문제들[편집]

경로 문제[편집]

Network Flow[편집]

..

Visibility graph problems[편집]

Max Flow - Min Cut[편집]

같이 보기[편집]

바깥 고리[편집]