개념 정의
그래프이론(Graph Theory)은 정점(vertex)이라 불리는 객체와 이들을 연결하는 간선(edge)이라 불리는 객체들의 집합으로 구성된 그래프라는 수학적 구조를 연구하는 학문 분야이다. 그래프는 이산 수학의 한 영역으로, 다양한 형태의 네트워크를 모델링하고 분석하는 데 사용된다.
주요 내용
| 구분 | 내용 |
|---|---|
| 기본 개념 | 정점, 간선, 무방향 그래프, 방향 그래프(유향 그래프), 가중치 그래프, 멀티그래프, 하이퍼그래프 등 |
| 핵심 문제 | 최단 경로(다익스트라, 벨만‑포드), 최소 신장 트리(크루스칼, 프림), 매칭(헝가리 알고리즘), 네트워크 흐름(포드‑풀커슨), 그래프 색칠(四色 정리) |
| 이론적 결과 | 오일러 회로와 경로, 파인만의 포레스트 정리, 마테오지니 수, 카라테오리 정리, 그래프 동형성 문제 등 |
| 응용 분야 | 컴퓨터 네트워크, 소셜 네트워크 분석, 전력·통신망 설계, 생물학적 네트워크(단백질 상호작용), 물류·경로 최적화, 사진·영상 처리, 인공지능(그래프 신경망) 등 |
역사
- 18세기: 레온하르트 오일러가 1736년 코니히 다리 문제를 통해 최초로 그래프 개념을 도입하였다. 이는 그래프이론의 시초로 간주된다.
- 20세기 초: 구스타프 푸리에와 폴 에르되시가 그래프의 구조적 성질을 연구하면서 현대 그래프이론의 토대를 마련하였다.
- 1930~1940년대: 폴 카라테오리와 매튜 벨라가 그래프 색칠 문제와 플래너리 그래프에 대한 정리를 제시하였다.
- 1970년대 이후: 컴퓨터 과학의 발달과 함께 알고리즘 연구가 급속히 진행되었으며, 현재 그래프이론은 이론 컴퓨터 과학, 최적화 이론, 데이터 과학 등 다방면에서 핵심적인 역할을 수행한다.
어원
‘그래프’(graph)는 영어 graph에서 차용되었으며, 이는 ‘그림, 도표’를 의미한다. ‘그래프이론’은 영어 graph theory의 직역으로, ‘그래프에 관한 이론’이라는 의미이다. 한국어에서는 20세기 후반부터 학술 서적 및 교육 과정에 정식 용어로 채택되었다.
학술적 지위
그래프이론은 수학·컴퓨터 과학 분야에서 독립적인 학문 분야로 인정받으며, 국제적으로는 Journal of Graph Theory, Discrete Mathematics, SIAM Journal on Discrete Mathematics 등에서 활발히 연구 결과가 발표된다. 또한 국제 학술 대회인 International Symposium on Graph Drawing(GD)와 Conference on Algorithms and Theory of Computation(SAT) 등에서 주요 주제로 다루어진다.
