그래프 (조합론)

그래프는 수학의 한 분야인 조합론 및 그래프 이론에서 객체들 사이의 이진 관계를 모델링하기 위해 사용되는 추상적인 수학적 구조이다. 기본적으로 정점(Vertex 또는 Node)과 그 정점들을 잇는 간선(Edge 또는 Link)의 집합으로 정의된다.

1. 정의 및 구성 요소 수학적으로 그래프 $G$는 $G = (V, E)$로 표현된다. 여기서 $V$는 정점들의 공집합이 아닌 유한 집합이며, $E$는 $V$에 속하는 정점들의 쌍으로 이루어진 간선들의 집합이다. 정점은 대상 자체를 나타내고, 간선은 두 대상 사이의 특정한 관계나 연결성을 나타낸다.

2. 주요 분류

• 무향 그래프(Undirected Graph): 간선에 방향이 없어 두 정점 사이의 관계가 대칭적인 경우이다. 간선 ${u, v}$는 $u$에서 $v$로의 연결과 $v$에서 $u$로의 연결을 동시에 의미한다.
• 유향 그래프(Directed Graph 또는 Digraph): 간선에 방향성이 존재하여 순서가 있는 정점 쌍 $(u, v)$로 표현된다. 이는 $u$에서 $v$로 향하는 일방향적인 관계를 의미한다.
• 가중치 그래프(Weighted Graph): 각 간선에 수치적 값(가중치)이 부여된 그래프로, 거리, 비용, 용량 등을 나타낼 때 사용된다.

3. 주요 개념

• 차수(Degree): 하나의 정점에 연결된 간선의 개수이다. 유향 그래프에서는 들어오는 간선의 수(진입 차수)와 나가는 간선의 수(진출 차수)로 구분한다.
• 경로(Path): 인접한 정점들을 따라 이동하는 정점과 간선의 순열이다.
• 회로(Cycle): 시작 정점과 끝 정점이 같은 경로를 의미한다.
• 연결성(Connectivity): 그래프 내의 임의의 두 정점 사이에 경로가 존재하는 상태를 뜻한다.

4. 역사 및 활용 그래프 이론은 1736년 레온하르트 오일러가 '쾨니히스베르크의 다리 문제'를 수학적으로 증명하면서 시작된 것으로 간주된다. 현대에는 컴퓨터 과학의 데이터 구조 및 알고리즘(최단 경로 탐색, 네트워크 유량 등), 사회과학의 인맥 지도 분석, 생물학의 단백질 상호작용 네트워크, 화학의 분자 구조 모델링 등 광범위한 분야에서 활용되고 있다.