정의
그래프는 정점(vertex)들의 집합 $V$와 정점들을 잇는 간선(edge)들의 집합 $E$의 순서쌍 $(V, E)$ 로 정의된다. 여기서 간선은 두 정점을 연결하는 2‑원소 집합으로 보는 경우가 일반적이며, 방향이 지정된 경우에는 순서쌍으로 나타낸다. 그래프 이론은 이러한 구조를 연구하는 조합론의 한 분야이다.
역사
그래프 이론은 1736년 레온하르트·오일러가 쾨니히스베르크의 일곱 다리 문제를 해결하면서 시작된 것으로 알려져 있다. 이는 최초의 그래프(연결된 정점과 간선)의 사례라 할 수 있다. 19세기 후반에 윌리엄·시얼프리드·시얼프리드·시알리(Sylvester)가 “graph”라는 용어를 도입하였으며, 1930년대에 프랭크·하라리(Frank Harary)와 같은 학자들이 현대적인 그래프 이론을 체계화하였다.
주요 개념
| 개념 | 설명 |
|---|---|
| 정점 (vertex, node) | 그래프를 구성하는 기본 단위. |
| 간선 (edge, arc) | 두 정점을 연결하는 관계. 무방향 그래프에서는 순서가 없고, 방향 그래프(디그래프)에서는 순서가 있다. |
| 단순 그래프 (simple graph) | 자기 루프와 다중 간선이 없는 그래프. |
| 다중 그래프 (multigraph) | 두 정점 사이에 여러 개의 간선이 허용되는 그래프. |
| 가중치 그래프 (weighted graph) | 각 간선에 실수값(가중치)이 부여된 그래프. |
| 연결성 (connectivity) | 그래프가 하나의 연결 요소로 이루어져 있는지 여부. |
| 차수 (degree) | 한 정점에 연결된 간선의 수. 방향 그래프에서는 진입 차수와 진출 차수를 구분한다. |
| 플래너 그래프 (planar graph) | 평면에 겹치지 않게 그릴 수 있는 그래프. |
| 그래프 색채 (graph coloring) | 정점이나 간선에 색을 배정해 인접한 정점(또는 간선)이 같은 색을 갖지 않게 하는 문제. |
| 인접 행렬 (adjacency matrix) | 정점 간의 연결 관계를 0‑1 행렬 또는 가중치 행렬로 나타낸 것. |
| 인접 리스트 (adjacency list) | 각 정점마다 인접한 정점들의 목록을 저장하는 방식. |
주요 정리·정리법
- 오일러 정리: 연결된 그래프에서 모든 정점의 차수가 짝수이면, 그 그래프는 오일러 회로(모든 간선을 한 번씩만 지나면서 시작점으로 돌아오는 경로)를 갖는다.
- 켈리의 정리: 그래프가 트리(사이클이 없고 연결된 그래프)라면 $|E| = |V| - 1$ 이다.
- 색채 정리(브루어스-코프만 정리): 평면 그래프는 최대 4가지 색으로 정점 색채가 가능하다.
응용 분야
- 컴퓨터 과학: 네트워크 설계, 데이터 구조(트리, 힙), 알고리즘(다익스트라, 프림, 크루스칼 등)
- 통신 및 전기공학: 회로 설계, 라우팅 최적화
- 생물학: 유전자·단백질 상호작용 네트워크, 진화 트리
- 사회과학: 소셜 네트워크 분석, 전파 모델링
- 화학: 분자 구조를 그래프(화학 그래프)로 모델링
관련 분야
- 조합론: 그래프의 계수 문제(예: 그래프의 개수 세기)와 연결
- 확률론: 무작위 그래프 모델(예: 에르되시–레니 모델)
- 최적화: 그래프 기반 최적화 문제(예: 최소 신장 트리, 최대 흐름)
참고 문헌·출처
- Diestel, R. Graph Theory, 5th ed., Springer, 2017.
- West, D. B. Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
- 하라리, 프랭크. 그래프 이론 (Graph Theory), 한국과학기술원 출판부, 1990.
본 항목은 현재까지 확인된 공신력 있는 자료에 근거하여 작성되었으며, 추가적인 최신 연구가 반영될 경우 내용이 갱신될 수 있다.