그래프 (그래프 이론)

정의: 그래프 이론에서의 그래프는 노드(node) 또는 정점(vertex)이라고 불리는 객체들의 집합과, 그 노드들을 연결하는 에지(edge) 또는 간선이라고 불리는 연결들의 집합으로 구성된 수학적 구조이다. 그래프는 다양한 현상과 관계를 모델링하는 데 사용되며, 컴퓨터 과학, 통계학, 물리학 등 다양한 분야에서 중요한 역할을 한다.

유형:

• 무방향 그래프 (Undirected Graph): 에지가 방향성을 갖지 않는 그래프. 노드 A와 B를 연결하는 에지는 A에서 B로, B에서 A로 동일하게 연결을 나타낸다.
• 방향 그래프 (Directed Graph) 또는 유향 그래프: 에지가 방향성을 갖는 그래프. 노드 A에서 B로 향하는 에지는 A에서 B로의 연결만을 나타낸다. 이는 A에서 B로의 일방향 관계를 표현하는 데 사용된다.
• 가중 그래프 (Weighted Graph): 각 에지에 가중치(weight)가 할당된 그래프. 이 가중치는 거리, 비용, 강도 등 다양한 의미를 가질 수 있다.
• 완전 그래프 (Complete Graph): 모든 노드 쌍이 에지로 연결된 그래프.
• 비순환 그래프 (Acyclic Graph): 사이클(cycle), 즉 시작 노드와 끝 노드가 같은 경로가 없는 그래프. 트리(Tree)는 비순환 그래프의 특별한 경우이다.
• 연결 그래프 (Connected Graph): 그래프 내의 모든 노드 쌍이 경로로 연결된 그래프. 연결되지 않은 그래프는 여러 개의 연결 요소로 나눌 수 있다.

용어:

• 노드 (Node) 또는 정점 (Vertex): 그래프의 기본 구성 요소.
• 에지 (Edge) 또는 간선: 두 노드를 연결하는 연결.
• 차수 (Degree): 무방향 그래프에서 한 노드에 연결된 에지의 수.
• 진입 차수 (In-degree): 방향 그래프에서 한 노드로 들어오는 에지의 수.
• 출차수 (Out-degree): 방향 그래프에서 한 노드에서 나가는 에지의 수.
• 경로 (Path): 노드들의 순서열로, 각 노드 쌍은 에지로 연결되어 있다.
• 사이클 (Cycle): 시작 노드와 끝 노드가 같은 경로.
• 트리 (Tree): 연결된 비순환 그래프.

응용:

그래프는 사회 네트워크 분석, 지도 및 경로 찾기, 컴퓨터 네트워크 모델링, 알고리즘 설계 등 다양한 분야에서 널리 활용된다. 특히 최단 경로 알고리즘, 최대 유량 알고리즘 등 다양한 그래프 알고리즘이 개발되어 문제 해결에 사용된다.

관련 개념: 트리, 네트워크, 탐색 알고리즘 (예: 깊이 우선 탐색, 너비 우선 탐색), 최단 경로 알고리즘 (예: 다익스트라 알고리즘, 플로이드-워셜 알고리즘)