07_Graph (이산수학)

1. 그래프의 정의: 07_Graph (이산수학)
2. 그래프의 표현: 08_Graph (자료구조)
3. Graph Algorithms
   • Graph Traversal Algorithms
     • BFS (Breadth-First Search), 인접 리스트 $O(V+E)$
     • DFS (Depth-First Search), 인접 리스트 $O(V+E)$
   • MST Algorithms
     • Kruskal’s Algorithm, $O(E\lg E)$
     • Prim’s Algorithm, 우선순위 큐 $O(E\lg V)$
   • SSSP (Single-Source Shortest Path Algorithms)
     • (음수 가중치 X) Dijkstra’s Algorithm, 우선순위 큐 $O(E\lg V)$
     • (음수 가중치 O) Bellman-Ford Algorithm, $O(VE)$
   • APSP (All-Pairs Shortest Path Algorithms)
     • Floyd-Warshall Algorithm, $O(V^3)$

1. 그래프의 기본 개념

• Graph $G=(V,E)$
  • 정점들의 집합 $V$ (vertex; node)
  • 간선들의 집합 $E$ (edge; link, arc)

연결된 객체 사이의 관계를 표현하며, 범용성이 매우 뛰어나다.

1.1. 간선의 방향

1. 무방향 그래프 (Undirected Graph)

   • 양방향 간선
   • 간선 $(u,v)=(v,u)$
   • 자기 루프(self-loop) 없음: $(v,v)\notin E$

2. 방향 그래프 (Directed Graph; Diagraph)

   • 단방향 간선
   • Ordered Pair 표현의 간선 $⟨u,v⟩\ne ⟨v,u⟩$
   • 자기 루프(self-loop) 허용

1.2. 간선의 가중치

1. 무가중치 그래프 (Unweighted Graph)

2. 가중치 그래프 (Weighted Graph)

   • 간선마다 가중치/비용/거리 등을 할당한 그래프
   • 각 간선에 가중치 함수 $w:E\to R$

1.3. 정점의 차수

• 어떤 정점 $v$에 부속된/인접하는 간선의 수 $\text{deg}(v)$를 차수(Degree)라고 한다.

  • 차수가 0인 정점을 고립 정점(Isolated Vertex)이라고 한다.

  • 차수가 1인 정점을 끝 정점(End-vertex)이라고 한다.

  • 루프는 차수에 2만큼 기여한다.

  • 모든 정점의 차수가 $k$이면 k차 정규 그래프라고 한다.

• 무방향 그래프의 차수

  • 전체 차수에 대해 악수 정리가 성립한다.

• 방향 그래프의 차수

  • 진입 차수(In-degree; $\text{outdeg}(v)$)

  • 진출 차수(Out-degree; $\text{indeg}(v)$)로 계산한다.

  • In-degree가 0인 정점을 **소스(Source)**라고 한다.

  • Out-degree가 0인 정점을 **싱크(Sink)**라고 한다.

  • 악수 딜레마

1.4. 한 정점 쌍 사이 간선의 수

1. 멀티 그래프

   • 간선의 개수 제한이 없음

2. 단순 그래프

   • 많아도 하나의 간선

1.5. 인접

• 인접 (Adjacency)

  • $(u,v)\in E$이면 정점 $v$는 정점 $u$에 인접
  • 무방향 그래프: 대칭적 관계
  • 방향 그래프: 대칭 관계 아닐 수 있음

• 인접 정점 (Adjacent vertex)

  • 한 정점에서 간선으로 직접 연결된 정점
  • $(v,w)\in E$이면 $v$와 $w$는 인접, 이 간선에 부속(incident)

• 인접 간선

  • 공통 정점을 가지는 두 간선

1.6. 전체 간선 수의 따른 구분

1. 희소 그래프 (Sparse Graph)

   • $|E|<<|V{|}^2$ (간선이 적음)

2. 밀집 그래프 (Dense Graph)

   • $|E|\approx |V{|}^2$ (간선이 많음)

2. 그래프의 용어

2.1. 부분집합 관계

• 부분 그래프 (Subgraph)

  • 원본 그래프의 정점과 간선의 부분 집합으로 이루어진 그래프

• 생성 부분 그래프 (Spanning Subgraph)

  • 부분 그래프로 생성할 수 있는 그래프 (예: 원본 그래프)

2.2. 그래프의 연결성

1. Disconnected Graph (비연결 그래프)

   • 그래프 내에 경로가 존재하지 않는 정점 쌍이 하나 이상 존재하는 그래프

   • (즉, 그래프가 둘 이상의 조각으로 쪼개져 있는 상태)

   • 주로 무방향 그래프(Undirected Graph)에서 정의

   • 특정 정점군에서 다른 정점군으로 이동할 수 있는 간선이 존재하지 않는다.

2. Connected Graph (연결 그래프)

   • 그래프 내의 모든 임의의 두 정점 $u$와 $v$ 사이에 경로(Path)가 항상 존재하는 그래프

   • 주로 무방향 그래프(Undirected Graph)에서 정의

   • (방향 그래프 $D$의 기반 무방향 그래프가 연결되어 있는 경우)

   • 고립되어 도달할 수 없는 정점이 없으며, 모든 노드가 하나의 커다란 네트워크로 이어져 있다.

   • 어느 한 노드에서 출발하더라도 간선을 따라 이동하면 다른 모든 노드로 도달할 수 있다.

   • $|E|\ge |V|-1$

3. Strongly Connected Graph (강연결 그래프)

   • 방향 그래프 내의 모든 임의의 두 정점 $u$와 $v$에 대해, $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재하는 그래프

   • 방향 그래프(Directed Graph)에서 정의

   • 모든 정점 쌍 사이에 양방향으로 왕복할 수 있는 경로가 존재

4. Complete Graph (완전 그래프; $K_n$)

   • 그래프 내의 모든 서로 다른 정점 쌍이 직접 하나의 간선(Edge)으로 연결되어 있는 그래프
   • 정점 $n$개에 대해 간선의 총 개수는 $\frac{n\times (n-1)}{2}$

2.3. 경로/순회

용어	중복 ❌	Cycle	모든 통과	존재성
단순 경로	간선 중복 ❌	-	-	-
단순 순회	간선 중복 ❌	✅	-	-
오일러 경로	간선 중복 ❌	-	모든 간선 통과	오일러의 정리
오일러 순회	간선 중복 ❌	✅	모든 간선 통과	오일러의 정리
기본 경로	정점 중복 ❌	-	-	-
기본 순회	정점 중복 ❌	✅	-	-
해밀턴 경로	정점 중복 ❌	-	모든 정점 통과	-
해밀턴 순회	정점 중복 ❌	✅	모든 정점 통과	-

• 경로 (Path)

  • 정점들의 나열로, 인접한 정점들 사이에 간선이 존재해야 함

• 단순 경로

  • 반복되는 간선이 없는 경로

• 순회 (Cycle)

  • 시작 정점과 종료 정점이 동일한 경로

• 오일러 그래프 (Eulerian Graph)

  • 모든 간선(edge)을 정확히 한 번씩 지나 시작점으로 돌아오는 경로 존재
  • 오일러 경로 존재성 → 오일러의 정리: 차수가 홀수인 정점이 0개 또는 2개

• 해밀턴 그래프 (Hamiltonian Graph)

  • 모든 정점(vertex)을 정확히 한 번씩 방문하고 시작점으로 돌아오는 경로 존재

2.4. 기타 정의

• 동형 (Isomorphic)

  • 두 digraph의 기본 그래프 사이에 정점 순서를 보존하는 동형사상(isomorphism)이 존재

• 방향 가능 (Orientable)

  • 그래프의 각 간선에 방향을 부여하여 strongly connected digraph로 만들 수 있는 그래프 $G$
  • 오일러 그래프는 항상 orientable

3. Special Graphs

3.1. 트리

• 트리 (Tree)

  • 모든 정점 쌍 사이에, 정확히 하나의 경로가 존재하는(사이클이 없는) 연결 그래프
  • $|E|=|V|-1$

• 트리의 루트 노드

  • 루트로부터 다른 모든 노드로 가는 경로가 항상 유일하게 존재함
  • 루트로 들어오는 연결선이 없으므로 루트는 모든 트리의 출발점이 됨

3.2. 신장 트리

• 신장 트리 (Spanning Tree)

  • 연결 그래프 $G$의 모든 정점을 포함하면서 사이클이 없는 부분 그래프(트리)

• 신장 트리의 성질

  • 정점이 $V$개이면 간선은 정확히 $V-1$개
  • 하나의 그래프에서 신장 트리는 여러 개 존재 가능
  • DFS 또는 BFS로 탐색하면서 트리를 구성

3.3. MST

• 최소 신장 트리 (Minimum Spanning Tree, MST)

  • 모든 신장 트리 중 간선 가중치의 합이 최소인 것

• 최소 신장 트리의 성질

  • 간선의 수: $|V|-1$

  • 사이클 없음

  • 유일하지 않을 수 있음

  • 최적 부분구조 만족: MST의 부분 트리도 해당 서브그래프의 MST

• 그래프 모델

  • 무방향 그래프 G = (V, E)
  • 각 간선 (u, v)에 가중치 w(u, v) 존재
  • T ⊆ E를 찾되, T가 모든 정점을 연결(신장 트리)하고, 가중치의 합 w(T)를 최소화

3.4. 이분 그래프

• 이분 그래프

  • 그래프가 두 부분 집합으로 나누어져 각 간선이 쌍으로 연결

• 완전 이분 그래프

  • 집합 내 모든 정점들 사이에 간선이 존재

3.5. 평면 그래프

• 동형 그래프

  • 같은 위상의 그래프
  • 예: 원래 그래프와 평면 그래프는 서로 동형 그래프이다.

• 평면 그래프 (Planar Graph)

  • 평면 상에서, 어떠한 간선도 서로 교차하지 않고 다시 그릴 수 있는 그래프
  • 오일러의 정리: 정점의 수 v - 연결선의 수 e + 면의 수 f = 2
  • 면의 수는 그래프 바깥에 있는 평면까지 포함

4. 그래프의 응용

4.0. P-NP 문제

• P-NP 문제
  • 컴퓨터 과학과 수학에서 가장 유명한 미해결 문제 중 하나
  • 핵심 질문: “빠르게 검증할 수 있는 문제는 빠르게 풀 수도 있는가?”

1. P (Polynomial)

   • 다항 시간 안에 풀 수 있는 문제들의 집합이다.
   • 컴퓨터가 효율적으로 해결할 수 있는 “쉬운” 문제들로, 정렬, 최단경로(다익스트라), 최대공약수 계산 등이 여기에 속한다.

2. NP (Nondeterministic Polynomial)

   • 답이 주어졌을 때 그것이 맞는지 검증을 다항 시간에 할 수 있는 문제들의 집합이다.
   • P ⊆ NP이므로 P에 속한 문제는 모두 NP에도 속한다. (풀 수 있으면 검증도 할 수 있으니까)
   • 스도쿠나 퍼즐 정답 확인이 직관적인 예시이다.
   • “P=NP인가, P≠NP인가”는 컴퓨터 과학 최대의 미해결 문제이다.

3. NP-난해 (NP-Hard)

   • NP에 속한 모든 문제를 다항 시간 내에 해당 문제로 변환(환원)할 수 있는 문제들이다.
   • 즉, “NP에서 가장 어렵거나 그 이상”인 문제들이다.
   • 단, 이 문제 자체가 NP에 속할 필요는 없다.
   • 외판원 문제(최적해 찾기), 정지 문제(결정 불가능) 등이 여기에 해당한다.

4. NP-완전 (NP-Complete)

   • NP이면서 동시에 NP-난해인 문제들이다.
   • 즉 NP ∩ NP-난해이다.
   • NP 중에서 “가장 어려운” 문제들의 집합으로, 만약 NP-완전 문제 하나라도 다항 시간에 풀린다면 P = NP가 증명된다.
   • SAT(불리언 만족 가능성), 3-색칠 문제, 배낭 문제 등이 대표적이다.

4.1. Travelling Salesman Problem

• 해밀턴 순회 문제

  • 결정형 TSP: NP-Complete
  • 최적화형 TSP: NP-Hard

• Nearest Neighbor

  • 가장 가까운 정점으로 이동을 반복하여 순회
  • 최적해가 보장되지 않는 근사 알고리즘

4.2. 그래프와 색칠 문제

• 4색 문제
  • (지도의 영역 → 인접 그래프)
  • 모든 평면 그래프는 네 가지 색으로 색칠이 가능하다.