그래프 이론
From CS Wiki
그래프 이론(Graph Theory)은 정점(Vertex)과 간선(Edge)으로 이루어진 그래프(Graph)를 연구하는 수학의 한 분야이다. 그래프는 객체 간의 관계를 나타내는 구조로, 컴퓨터 과학, 네트워크, 운영 연구, 생물학, 사회학 등 다양한 분야에서 활용된다.
1 기본 개념[edit | edit source]
그래프는 두 개의 집합으로 정의된다.
- 정점(Vertex) 또는 노드(Node): 데이터를 저장하는 요소
- 간선(Edge): 정점 간의 연결을 나타내는 요소
그래프는 다음과 같은 형태로 분류된다.
1.1 1. 방향 그래프 vs. 무방향 그래프[edit | edit source]
- 방향 그래프(Directed Graph, 유향 그래프) → 간선이 특정한 방향성을 가짐
- 무방향 그래프(Undirected Graph, 무향 그래프) → 간선에 방향성이 없음
예시:
A — B (무방향 그래프) A → B (방향 그래프)
1.2 2. 가중치 그래프 vs. 비가중치 그래프[edit | edit source]
- 가중치 그래프(Weighted Graph) → 간선에 가중치(비용, 거리, 시간 등)가 존재함
- 비가중치 그래프(Unweighted Graph) → 간선에 가중치가 없음
1.3 3. 연결 그래프 vs. 비연결 그래프[edit | edit source]
- 연결 그래프(Connected Graph) → 모든 정점이 최소 한 개의 경로로 연결됨
- 비연결 그래프(Disconnected Graph) → 일부 정점이 다른 정점과 연결되지 않음
1.4 4. 방향 비순환 그래프(DAG)[edit | edit source]
- DAG(Directed Acyclic Graph) → 방향성을 가지며 순환이 없는 그래프
- 위상 정렬 등에 사용됨
2 그래프 표현 방법[edit | edit source]
그래프는 여러 가지 방법으로 표현할 수 있다.
2.1 1. 인접 행렬 (Adjacency Matrix)[edit | edit source]
그래프를 2차원 배열로 표현하는 방법.
예제 (무방향 그래프): A B C A 0 1 1 B 1 0 1 C 1 1 0
2.2 2. 인접 리스트 (Adjacency List)[edit | edit source]
각 정점마다 연결된 정점들을 리스트로 표현하는 방법.
예제: A: [B, C] B: [A, C] C: [A, B]
3 주요 그래프 알고리즘[edit | edit source]
그래프를 탐색하고 분석하기 위해 다양한 알고리즘이 존재한다.
- 깊이 우선 탐색(DFS, Depth-First Search) → 스택 또는 재귀를 이용한 그래프 탐색
- 너비 우선 탐색(BFS, Breadth-First Search) → 큐를 이용한 그래프 탐색
- 최단 경로 알고리즘
- 다익스트라 알고리즘 → 단일 출발점 최단 경로 (O((V+E) log V))
- 벨만-포드 알고리즘 → 음수 가중치 포함 가능 (O(VE))
- 플로이드-워셜 알고리즘 → 모든 쌍 최단 경로 (O(V³))
- 최소 신장 트리(MST, Minimum Spanning Tree)
- 강한 연결 요소(SCC, Strongly Connected Components)
- 위상 정렬(Topological Sorting)
- 방향 비순환 그래프(DAG)에서 노드를 정렬하는 방법
4 트리와의 관계[edit | edit source]
트리는 그래프의 한 종류이므로 그래프 이론의 일부로 간주된다. 하지만 그래프 이론에서는 일반적인 그래프(Graph)를 연구하는 반면, 트리(Tree)는 그래프의 특별한 형태로서 별도의 연구 주제로 다뤄지기도 한다.
4.1 트리가 그래프 이론에서 별도로 다뤄지는 이유[edit | edit source]
트리는 그래프의 특수한 형태이지만, 그 자체로 중요한 성질을 가지기 때문에 그래프 이론과 별도로 연구되는 경우가 많다. 주요 차이점은 다음과 같다.
- 순환이 없음
- 트리는 사이클이 없는 연결 그래프이다.
- 모든 정점이 연결되어 있으며, 정확히 V-1개의 간선을 가진다 (V는 정점의 개수).
- 유형에 따른 차이
- 일반적인 그래프는 방향성과 가중치를 가질 수도 있지만, 트리는 보통 무방향이고 가중치가 없다고 가정하는 경우가 많다.
- 그러나 이진 트리(Binary Tree)나 이진 탐색 트리(BST) 같은 구조는 특정한 규칙을 따르며, 컴퓨터 과학에서 별도로 연구된다.
- 트리의 응용
- 트리는 그래프보다 특정 문제에서 더 효율적인 구조를 제공한다.
- 최소 신장 트리(MST, Minimum Spanning Tree)는 그래프에서 트리를 찾는 문제로, 크루스칼과 프림 알고리즘을 사용하여 해결한다.
- 데이터 구조로서의 트리(예: AVL 트리, B-트리)는 데이터베이스, 파일 시스템, 인덱싱 등의 응용에서 사용된다.
4.2 그래프 이론에서 트리를 포함할 때와 제외할 때[edit | edit source]
- 포함할 때
- 트리를 연결 무향 비순환 그래프(Connected Acyclic Undirected Graph)로 정의하고, 그래프 이론 내에서 연구할 수 있다.
- 스패닝 트리(Spanning Tree), 최소 신장 트리(MST), 루트가 있는 트리(Rooted Tree) 등은 그래프 이론과 밀접한 관련이 있다.
- 제외할 때
- 이진 트리, AVL 트리, B-트리처럼 '''데이터 구조로서의 트리'''를 연구하는 경우, 그래프 이론보다는 별도의 트리 이론(Tree Theory)으로 분리된다.
- 트리가 가지는 특정한 성질(예: 노드 삽입, 삭제, 회전 등)을 중심으로 연구할 때는 그래프보다는 데이터 구조에 가깝다.
5 코드 예제[edit | edit source]
아래는 BFS(너비 우선 탐색)의 구현 예제이다.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 예제 그래프 (무방향 그래프)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# BFS 실행
bfs(graph, 'A')
출력 결과 예시: A B C D E F
6 응용[edit | edit source]
그래프 이론은 여러 분야에서 활용된다.
- 컴퓨터 네트워크 → 네트워크 라우팅, 인터넷 구조 분석
- 소셜 네트워크 분석 → 친구 추천, 커뮤니티 탐색
- 운영 연구 → 작업 스케줄링, 최적화 문제 해결
- 컴퓨터 그래픽스 → 3D 모델의 폴리곤 연결 구조
- 생물정보학 → 단백질 상호작용 네트워크 분석
7 같이 보기[edit | edit source]
8 참고 문헌[edit | edit source]
- Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
- Harary, Frank. "Graph Theory." Addison-Wesley, 1969.