그래프 이론(Graph Theory)은 객체 간의 관계를 수학적으로 모델링하는 분야로, 컴퓨터 과학, 네트워크, 생물학, 사회학 등 다양한 분야에 응용됩니다. 이 글에서는 그래프 이론의 기초 개념과 용어를 중심으로 핵심 개념들을 정리합니다.
1. 그래프의 정의
그래프는 정점(Vertex)과 간선(Edge)으로 구성된 구조입니다. 일반적으로 다음과 같이 표현됩니다: \[ G = (V, E) \] 여기서 V는 정점들의 집합, E는 정점 쌍의 집합(간선)입니다.
- 무방향 그래프: 간선이 방향이 없음 (예: 친구 관계)
- 방향 그래프: 간선이 방향을 가짐 (예: 팔로우 관계)
2. 주요 용어 정리
- 정점(Vertex): 연결된 대상 (노드라고도 함)
- 간선(Edge): 정점 간의 연결
- 차수(Degree): 한 정점에 연결된 간선의 수
- 경로(Path): 정점과 간선이 순서대로 연결된 연속
- 사이클(Cycle): 시작점과 끝점이 같은 경로
- 연결 그래프(Connected Graph): 모든 정점이 서로 연결되어 있음
3. 그래프의 종류
- 단순 그래프: 중복 간선 없이, 자기 루프 없음
- 가중치 그래프: 간선마다 비용 또는 거리 등의 값이 있음
- 이중 그래프(Bipartite Graph): 정점이 두 집합으로 나뉘어 있고, 같은 집합 내에서는 간선 없음
- 완전 그래프(Complete Graph): 모든 정점 쌍이 간선으로 연결됨
4. 표현 방법
그래프는 다음과 같은 방식으로 표현할 수 있습니다:
- 인접 행렬 (Adjacency Matrix): \( n \times n \) 행렬로, 두 정점 간 연결 여부 표시
- 인접 리스트 (Adjacency List): 각 정점에 연결된 정점 목록으로 표현
5. 기본 알고리즘
- 깊이 우선 탐색(DFS): 가능한 깊이까지 탐색 후 되돌아옴
- 너비 우선 탐색(BFS): 인접 정점부터 넓게 탐색
- 최단 경로 알고리즘: 다익스트라, 벨만-포드 등
- 최소 신장 트리(MST): 크루스칼, 프림 알고리즘 등
결론
그래프 이론은 단순한 정점과 간선의 연결에서 시작하지만, 다양한 구조와 알고리즘을 통해 복잡한 관계와 네트워크를 분석하고 해결할 수 있는 강력한 도구입니다. 기초 개념을 이해하면 이후 경로 탐색, 최적화 문제, 네트워크 분석 등 다양한 분야로 확장할 수 있습니다.