그래프 이론 편집하기

'''그래프 이론'''(Graph Theory)은 정점(Vertex)과 간선(Edge)으로 이루어진 '''그래프'''(Graph)를 연구하는 수학의 한 분야이다. 그래프는 객체 간의 관계를 나타내는 구조로, 컴퓨터 과학, 네트워크, 운영 연구, 생물학, 사회학 등 다양한 분야에서 활용된다.
==기본 개념==
그래프는 두 개의 집합으로 정의된다.
*'''정점(Vertex)''' 또는 '''노드(Node)''': 데이터를 저장하는 요소
*'''간선(Edge)''': 정점 간의 연결을 나타내는 요소
그래프는 다음과 같은 형태로 분류된다.
===1. 방향 그래프 vs. 무방향 그래프===
*'''방향 그래프'''(Directed Graph, 유향 그래프) → 간선이 특정한 방향성을 가짐
*'''무방향 그래프'''(Undirected Graph, 무향 그래프) → 간선에 방향성이 없음
예시:
 A — B  (무방향 그래프)  
 A → B  (방향 그래프)  
===2. 가중치 그래프 vs. 비가중치 그래프===
*'''가중치 그래프'''(Weighted Graph) → 간선에 가중치(비용, 거리, 시간 등)가 존재함
*'''비가중치 그래프'''(Unweighted Graph) → 간선에 가중치가 없음
===3. 연결 그래프 vs. 비연결 그래프===
*'''연결 그래프'''(Connected Graph) → 모든 정점이 최소 한 개의 경로로 연결됨
*'''비연결 그래프'''(Disconnected Graph) → 일부 정점이 다른 정점과 연결되지 않음
===4. 방향 비순환 그래프(DAG)===
*'''DAG(Directed Acyclic Graph)''' → 방향성을 가지며 순환이 없는 그래프
*위상 정렬 등에 사용됨
==그래프 표현 방법==
그래프는 여러 가지 방법으로 표현할 수 있다.
===1. 인접 행렬 (Adjacency Matrix)===
그래프를 2차원 배열로 표현하는 방법.
 예제 (무방향 그래프):
   A B C  
 A 0 1 1  
 B 1 0 1  
 C 1 1 0  
===2. 인접 리스트 (Adjacency List)===
각 정점마다 연결된 정점들을 리스트로 표현하는 방법.
 예제:
 A: [B, C]  
 B: [A, C]  
 C: [A, B]  
==주요 그래프 알고리즘==
그래프를 탐색하고 분석하기 위해 다양한 알고리즘이 존재한다.
*'''[[깊이 우선 탐색|깊이 우선 탐색(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)에서 노드를 정렬하는 방법

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

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

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

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

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

==코드 예제==
아래는 BFS(너비 우선 탐색)의 구현 예제이다.<syntaxhighlight lang="python">
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')
</syntaxhighlight>
 출력 결과 예시:
 A B C D E F  
==응용==
그래프 이론은 여러 분야에서 활용된다.
*'''컴퓨터 네트워크''' → 네트워크 라우팅, 인터넷 구조 분석
*'''소셜 네트워크 분석''' → 친구 추천, 커뮤니티 탐색
*'''운영 연구''' → 작업 스케줄링, 최적화 문제 해결
*'''컴퓨터 그래픽스''' → 3D 모델의 폴리곤 연결 구조
*'''생물정보학''' → 단백질 상호작용 네트워크 분석
==같이 보기==
*[[깊이 우선 탐색]]
*[[너비 우선 탐색]]
*[[최단 경로 알고리즘]]
*[[최소 신장 트리]]
*[[위상 정렬]]
==참고 문헌==
*Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
*Harary, Frank. "Graph Theory." Addison-Wesley, 1969.
[[분류:알고리즘]]