그래프 이론

그래프 이론(Graph Theory)은 정점(Vertex)과 간선(Edge)으로 이루어진 그래프(Graph)를 연구하는 수학의 한 분야이다. 그래프는 객체 간의 관계를 나타내는 구조로, 컴퓨터 과학, 네트워크, 운영 연구, 생물학, 사회학 등 다양한 분야에서 활용된다.

1 기본 개념

그래프는 두 개의 집합으로 정의된다.

• 정점(Vertex) 또는 노드(Node): 데이터를 저장하는 요소
• 간선(Edge): 정점 간의 연결을 나타내는 요소

그래프는 다음과 같은 형태로 분류된다.

1.1 1. 방향 그래프 vs. 무방향 그래프

• 방향 그래프(Directed Graph, 유향 그래프) → 간선이 특정한 방향성을 가짐
• 무방향 그래프(Undirected Graph, 무향 그래프) → 간선에 방향성이 없음

예시:

A — B  (무방향 그래프)  
A → B  (방향 그래프)  

1.2 2. 가중치 그래프 vs. 비가중치 그래프

• 가중치 그래프(Weighted Graph) → 간선에 가중치(비용, 거리, 시간 등)가 존재함
• 비가중치 그래프(Unweighted Graph) → 간선에 가중치가 없음

1.3 3. 연결 그래프 vs. 비연결 그래프

• 연결 그래프(Connected Graph) → 모든 정점이 최소 한 개의 경로로 연결됨
• 비연결 그래프(Disconnected Graph) → 일부 정점이 다른 정점과 연결되지 않음

1.4 4. 방향 비순환 그래프(DAG)

• DAG(Directed Acyclic Graph) → 방향성을 가지며 순환이 없는 그래프
• 위상 정렬 등에 사용됨

2 그래프 표현 방법

그래프는 여러 가지 방법으로 표현할 수 있다.

2.1 1. 인접 행렬 (Adjacency Matrix)

그래프를 2차원 배열로 표현하는 방법.

예제 (무방향 그래프):
  A B C  
A 0 1 1  
B 1 0 1  
C 1 1 0  

2.2 2. 인접 리스트 (Adjacency List)

각 정점마다 연결된 정점들을 리스트로 표현하는 방법.

예제:
A: [B, C]  
B: [A, C]  
C: [A, B]  

3 주요 그래프 알고리즘

그래프를 탐색하고 분석하기 위해 다양한 알고리즘이 존재한다.

• 깊이 우선 탐색(DFS, Depth-First Search) → 스택 또는 재귀를 이용한 그래프 탐색
• 너비 우선 탐색(BFS, Breadth-First Search) → 큐를 이용한 그래프 탐색
• 최단 경로 알고리즘
  • 다익스트라 알고리즘 → 단일 출발점 최단 경로 (O((V+E) log V))
  • 벨만-포드 알고리즘 → 음수 가중치 포함 가능 (O(VE))
  • 플로이드-워셜 알고리즘 → 모든 쌍 최단 경로 (O(V³))

• 최소 신장 트리(MST, Minimum Spanning Tree)
  • 크루스칼 알고리즘 → 간선을 정렬하여 최소 신장 트리 구성 (O(E log E))
  • 프림 알고리즘 → 하나의 정점에서 시작하여 MST 구축 (O(V²) 또는 O((V+E) log V) with heap)

• 강한 연결 요소(SCC, Strongly Connected Components)
  • 타잔 알고리즘 → DFS 기반 (O(V+E))
  • 코사라주 알고리즘 → 역방향 그래프 활용 (O(V+E))

• 위상 정렬(Topological Sorting)
  • 방향 비순환 그래프(DAG)에서 노드를 정렬하는 방법

4 트리와의 관계

트리는 그래프의 한 종류이므로 그래프 이론의 일부로 간주된다. 하지만 그래프 이론에서는 일반적인 그래프(Graph)를 연구하는 반면, 트리(Tree)는 그래프의 특별한 형태로서 별도의 연구 주제로 다뤄지기도 한다.

4.1 트리가 그래프 이론에서 별도로 다뤄지는 이유

트리는 그래프의 특수한 형태이지만, 그 자체로 중요한 성질을 가지기 때문에 그래프 이론과 별도로 연구되는 경우가 많다. 주요 차이점은 다음과 같다.

1. 순환이 없음
   • 트리는 사이클이 없는 연결 그래프이다.
   • 모든 정점이 연결되어 있으며, 정확히 V-1개의 간선을 가진다 (V는 정점의 개수).
2. 유형에 따른 차이
   • 일반적인 그래프는 방향성과 가중치를 가질 수도 있지만, 트리는 보통 무방향이고 가중치가 없다고 가정하는 경우가 많다.
   • 그러나 이진 트리(Binary Tree)나 이진 탐색 트리(BST) 같은 구조는 특정한 규칙을 따르며, 컴퓨터 과학에서 별도로 연구된다.
3. 트리의 응용
   • 트리는 그래프보다 특정 문제에서 더 효율적인 구조를 제공한다.
   • 최소 신장 트리(MST, Minimum Spanning Tree)는 그래프에서 트리를 찾는 문제로, 크루스칼과 프림 알고리즘을 사용하여 해결한다.
   • 데이터 구조로서의 트리(예: AVL 트리, B-트리)는 데이터베이스, 파일 시스템, 인덱싱 등의 응용에서 사용된다.

4.2 그래프 이론에서 트리를 포함할 때와 제외할 때

• 포함할 때
  • 트리를 연결 무향 비순환 그래프(Connected Acyclic Undirected Graph)로 정의하고, 그래프 이론 내에서 연구할 수 있다.
  • 스패닝 트리(Spanning Tree), 최소 신장 트리(MST), 루트가 있는 트리(Rooted Tree) 등은 그래프 이론과 밀접한 관련이 있다.
• 제외할 때
  • 이진 트리, AVL 트리, B-트리처럼 '''데이터 구조로서의 트리'''를 연구하는 경우, 그래프 이론보다는 별도의 트리 이론(Tree Theory)으로 분리된다.
  • 트리가 가지는 특정한 성질(예: 노드 삽입, 삭제, 회전 등)을 중심으로 연구할 때는 그래프보다는 데이터 구조에 가깝다.

5 코드 예제

아래는 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 응용

그래프 이론은 여러 분야에서 활용된다.

• 컴퓨터 네트워크 → 네트워크 라우팅, 인터넷 구조 분석
• 소셜 네트워크 분석 → 친구 추천, 커뮤니티 탐색
• 운영 연구 → 작업 스케줄링, 최적화 문제 해결
• 컴퓨터 그래픽스 → 3D 모델의 폴리곤 연결 구조
• 생물정보학 → 단백질 상호작용 네트워크 분석

7 같이 보기

• 깊이 우선 탐색
• 너비 우선 탐색
• 최단 경로 알고리즘
• 최소 신장 트리
• 위상 정렬

8 참고 문헌

• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
• Harary, Frank. "Graph Theory." Addison-Wesley, 1969.