12.1 그래프의 정의와 기본 용어

1. 그래프의 직관적 이해

그래프(graph)는 객체들 사이의 관계를 표현하는 추상적 구조이며, 점(노드)과 그들을 연결하는 선(엣지)으로 구성된다. 일상생활에서 흔히 볼 수 있는 예로는 지도 위의 도시와 도로, 소셜 네트워크의 사람과 친구 관계, 컴퓨터 네트워크의 서버와 연결 등이 있다. 그래프는 이러한 다양한 시스템을 통일된 수학적 언어로 표현할 수 있게 한다. 로봇공학에서 그래프는 환경 표현, 운동학적 구조, 작업 계획, 다중 로봇 시스템 등 다양한 영역에서 핵심 도구이다.

2. 그래프의 형식적 정의

2.1 정의

그래프 $G$ 는 다음의 두 집합으로 정의된다.

$G = (V, E)$

여기서

$V$ : 노드(node) 또는 정점(vertex)의 집합
$E$ : 엣지(edge) 또는 변(arc)의 집합

엣지는 두 노드의 쌍이며, 두 노드 사이의 관계를 표현한다.

2.2 무방향 그래프

무방향 그래프(undirected graph)에서 엣지는 두 노드의 순서가 없는 쌍이다.

$e = \{u, v\}, \quad u, v \in V$

엣지 $\{u, v\}$ 와 $\{v, u\}$ 는 같은 엣지로 간주된다.

2.3 방향 그래프

방향 그래프(directed graph 또는 digraph)에서 엣지는 순서가 있는 쌍이다.

$e = (u, v), \quad u, v \in V$

엣지 $(u, v)$ 와 $(v, u)$ 는 다른 엣지이다. 첫 번째 노드 $u$ 는 시작 노드(또는 꼬리), 두 번째 노드 $v$ 는 끝 노드(또는 머리)라 한다.

3. 그래프의 시각적 표현

3.1 다이어그램

그래프는 일반적으로 다음과 같이 시각적으로 표현된다.

노드는 원이나 점으로 표시한다.
엣지는 선으로 표시한다.
무방향 엣지는 단순한 선이다.
방향 엣지는 화살표가 있는 선이다.

이러한 시각적 표현은 그래프의 구조를 직관적으로 이해하는 데 도움이 된다.

4. 노드와 엣지의 기본 용어

4.1 인접

두 노드가 같은 엣지로 연결되어 있으면 인접(adjacent)하다고 한다. 무방향 그래프에서 $\{u, v\} \in E$ 이면 $u$ 와 $v$ 는 인접하다.

4.2 입사

엣지가 노드에 연결되어 있으면 그 엣지는 노드에 입사(incident)한다고 한다.

4.3 이웃

노드 $v$ 의 이웃(neighborhood)은 $v$ 와 인접한 모든 노드의 집합이다.

$N(v) = \{u \in V : \{u, v\} \in E\}$

방향 그래프에서는 입력 이웃과 출력 이웃을 구분한다.

4.4 차수

노드 $v$ 의 차수(degree)는 그 노드에 입사한 엣지의 수이다.

$\deg(v) = |N(v)|$

방향 그래프에서는 입력 차수(in-degree)와 출력 차수(out-degree)를 구분한다.

4.5 차수 합

무방향 그래프에서 모든 노드의 차수의 합은 엣지 수의 두 배이다.

$\sum_{v \in V}\deg(v) = 2|E|$

이는 각 엣지가 두 개의 노드에 연결되기 때문이다. 이를 핸드셰이킹 보조정리(handshaking lemma)라 한다.

5. 특수한 그래프

5.1 단순 그래프

단순 그래프(simple graph)는 다음을 만족하는 그래프이다.

자기 루프(self-loop)가 없다(노드가 자기 자신과 연결되지 않는다).
다중 엣지(multiple edges)가 없다(같은 두 노드 사이에 한 개의 엣지만 있다).

대부분의 응용에서 단순 그래프가 사용된다.

5.2 다중 그래프

다중 그래프(multigraph)는 같은 두 노드 사이에 여러 개의 엣지를 허용한다.

5.3 의사 그래프

의사 그래프(pseudograph)는 자기 루프와 다중 엣지를 모두 허용한다.

6. 그래프의 종류

6.1 가중치 그래프

가중치 그래프(weighted graph)는 각 엣지에 실수 값(가중치)이 부여된 그래프이다.

$w : E \to \mathbb{R}$

가중치는 거리, 비용, 시간, 용량 등 다양한 의미를 가질 수 있다.

6.2 비가중치 그래프

비가중치 그래프(unweighted graph)는 엣지에 가중치가 없는 그래프이다. 모든 엣지가 동등하게 취급된다.

6.3 라벨 그래프

라벨 그래프(labeled graph)는 노드 또는 엣지에 라벨(이름이나 속성)이 부여된 그래프이다.

6.4 평면 그래프

평면 그래프(planar graph)는 평면에 엣지의 교차 없이 그릴 수 있는 그래프이다. 평면 그래프는 특별한 성질(예: 오일러 공식)을 가진다.

7. 부분 그래프

7.1 정의

그래프 $G = (V, E)$ 의 부분 그래프(subgraph)는 다음을 만족하는 그래프 $G' = (V', E')$ 이다.

$V' \subseteq V, \quad E' \subseteq E$

또한 $E'$ 의 모든 엣지는 $V'$ 의 노드들 사이에서 정의되어야 한다.

7.2 유도 부분 그래프

노드 집합 $V' \subseteq V$ 의 유도 부분 그래프(induced subgraph)는 $V'$ 의 노드들과 그 노드들 사이의 모든 엣지로 구성된다.

7.3 신장 부분 그래프

신장 부분 그래프(spanning subgraph)는 $V' = V$ 인 부분 그래프이다. 즉, 모든 노드를 포함하지만 일부 엣지만 사용한다.

8. 경로와 사이클

8.1 경로

경로(path)는 노드들의 수열 $v_0, v_1, \ldots, v_k$ 이며, 연속된 노드들이 엣지로 연결된다.

$\{v_i, v_{i+1}\} \in E, \quad i = 0, 1, \ldots, k-1$

경로의 길이는 엣지의 수 $k$ 이다. 가중치 그래프에서는 엣지 가중치의 합이 길이가 된다.

8.2 단순 경로

단순 경로(simple path)는 모든 노드가 서로 다른 경로이다. 즉, 한 노드를 두 번 이상 방문하지 않는다.

8.3 사이클

사이클(cycle)은 시작 노드와 끝 노드가 같은 경로이다. 일반적으로 나머지 노드는 모두 다르다.

8.4 단순 사이클

단순 사이클(simple cycle)은 시작과 끝을 제외하고 모든 노드가 서로 다른 사이클이다.

9. 연결성

9.1 연결 그래프

무방향 그래프가 연결(connected)되었다는 것은 임의의 두 노드 사이에 경로가 존재한다는 것이다.

9.2 연결 성분

연결되지 않은 그래프는 여러 개의 연결 성분(connected component)으로 분해된다. 각 연결 성분은 그 자체로 연결된 부분 그래프이다.

9.3 강한 연결 vs 약한 연결

방향 그래프에서는 두 가지 연결성이 정의된다.

강한 연결(strongly connected): 임의의 두 노드 사이에 방향 경로가 존재한다.
약한 연결(weakly connected): 방향을 무시한 무방향 그래프가 연결되어 있다.

10. 트리

10.1 정의

트리(tree)는 사이클이 없는 연결된 무방향 그래프이다. 동등하게 다음과 같이 정의된다.

$n$ 개의 노드를 가지고 $n - 1$ 개의 엣지를 가진 연결 그래프이다.
임의의 두 노드 사이에 유일한 경로가 존재한다.
사이클이 없으면서 최대한 많은 엣지를 가진 그래프이다.

10.2 루트 트리

루트 트리(rooted tree)는 한 노드가 루트로 지정된 트리이다. 다른 노드들은 루트에서의 거리에 따라 깊이를 가진다.

10.3 부모와 자식

루트 트리에서 노드 $v$ 의 부모(parent)는 루트에서 $v$ 로의 경로에서 $v$ 직전에 있는 노드이다. $v$ 의 자식(child)은 $v$ 의 이웃 중 부모가 아닌 노드이다.

10.4 잎과 내부 노드

잎(leaf)은 자식이 없는 노드이고, 내부 노드(internal node)는 적어도 하나의 자식을 가진 노드이다.

11. 그래프의 표현

11.1 인접 행렬

그래프의 인접 행렬(adjacency matrix)은 다음과 같이 정의된다.

$A_{ij} = \begin{cases}1 & \text{if } \{i, j\} \in E \\ 0 & \text{otherwise}\end{cases}$

가중치 그래프에서는 $A_{ij} = w(\{i, j\})$ 이다. 인접 행렬은 $|V| \times |V|$ 행렬이며, 무방향 그래프에서는 대칭이다.

11.2 인접 리스트

인접 리스트(adjacency list)는 각 노드에 대해 그 이웃의 리스트를 저장한다.

node 1: [2, 3, 5]
node 2: [1, 4]
node 3: [1, 5]
...

이 표현은 희소 그래프(엣지가 적은 그래프)에 효율적이다.

11.3 두 표현의 비교

측면	인접 행렬	인접 리스트
메모리	$O(\vert V\vert^2)$	$O(\vert V\vert + \vert E\vert)$
엣지 존재 확인	$O(1)$	$O(\deg(v))$
이웃 순회	$O(\vert V\vert)$	$O(\deg(v))$
적합한 그래프	밀집	희소

12. 동형사상

12.1 정의

두 그래프 $G_1 = (V_1, E_1)$ 과 $G_2 = (V_2, E_2)$ 가 동형(isomorphic)이라는 것은 일대일 대응 $f : V_1 \to V_2$ 가 존재하여 다음을 만족하는 것이다.

$\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2$

동형 그래프는 라벨이 다를 뿐 구조는 같은 그래프이다.

12.2 그래프 동형사상 문제

두 그래프가 동형인지 결정하는 문제는 일반적으로 어려운 문제이다. 다항 시간 알고리즘이 알려져 있지 않다.

13. 완전 그래프

13.1 정의

완전 그래프(complete graph) $K_n$ 은 모든 노드 쌍이 엣지로 연결된 그래프이다. $n$ 개의 노드를 가진 완전 그래프의 엣지 수는 다음과 같다.

$|E| = \binom{n}{2} = \frac{n(n-1)}{2}$

13.2 응용

완전 그래프는 모든 가능한 연결을 가진 시스템을 모델링하는 데 사용된다. 분산 시스템의 통신 패턴, 모든 도시 사이의 직접 연결 등이 예이다.

14. 이분 그래프

14.1 정의

이분 그래프(bipartite graph)는 노드 집합이 두 개의 분리된 부분 집합 $V_1$ 과 $V_2$ 로 분할되며, 모든 엣지가 두 부분 집합 사이에만 존재하는 그래프이다.

$V = V_1 \cup V_2, \quad V_1 \cap V_2 = \emptyset$

$E \subseteq V_1 \times V_2$

14.2 응용

이분 그래프는 두 종류의 객체 사이의 관계를 모델링하는 데 사용된다.

작업과 작업자의 할당
사람과 작업의 매칭
학생과 수업의 등록

15. 정규 그래프

15.1 정의

정규 그래프(regular graph)는 모든 노드의 차수가 같은 그래프이다. 모든 노드가 차수 $k$ 를 가지면 $k$ -정규 그래프라 한다.

15.2 예시

0-정규 그래프: 엣지가 없는 그래프
1-정규 그래프: 모든 노드가 정확히 하나의 엣지를 가진 그래프
정규 다각형: 사이클 그래프 (2-정규)
완전 그래프 $K_n$ : $(n-1)$ -정규 그래프

16. 그래프의 응용

16.1 도로 네트워크

도로 네트워크는 가장 직관적인 그래프 응용이다. 노드는 교차로, 엣지는 도로 구간이다. 가중치는 거리나 통과 시간이다.

16.2 소셜 네트워크

소셜 네트워크는 사람과 그들 사이의 관계를 그래프로 표현한다. 친구 관계, 팔로우 관계 등이 엣지로 표현된다.

16.3 컴퓨터 네트워크

컴퓨터 네트워크는 컴퓨터(노드)와 통신 링크(엣지)로 구성된다. 인터넷의 라우팅이 그래프 알고리즘에 의존한다.

16.4 의존 관계

작업의 의존 관계, 컴파일의 의존성, 모듈의 의존성 등이 방향 그래프로 표현된다.

16.5 분자 구조

화학에서 분자의 원자(노드)와 결합(엣지)이 그래프로 표현된다. 그래프 동형사상이 화학 구조 검색에 활용된다.

17. 로봇공학에서의 응용

17.1 환경 표현

로봇이 활동하는 환경은 종종 그래프로 표현된다. 격자, 보로노이 다이어그램, 가시성 그래프 등이 사용된다.

17.2 운동학적 구조

매니퓰레이터와 같은 로봇의 운동학적 구조는 트리 그래프이다. 링크는 노드, 관절은 엣지이다.

17.3 경로 계획

경로 계획에서 환경이 그래프로 표현되고, 최단 경로 알고리즘이 적용된다.

17.4 SLAM

자세 그래프 SLAM에서 그래프는 자세(노드)와 자세 사이의 측정(엣지)으로 구성된다.

17.5 다중 로봇 시스템

다중 로봇의 통신 네트워크와 작업 할당이 그래프로 모델링된다.

18. 그래프 이론의 학습 가치

그래프 이론을 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

다양한 시스템을 통일된 언어로 표현할 수 있다.
효율적인 알고리즘을 활용할 수 있다.
로봇공학의 다양한 문제를 모델링할 수 있다.
학술 문헌과 산업 표준을 이해할 수 있다.
새로운 응용을 개발할 수 있다.

19. 학습 권장사항

19.1 시각적 학습

그래프는 시각적 대상이므로 다이어그램을 그리며 학습하는 것이 효과적이다. 작은 예제부터 시작하여 점차 큰 그래프로 확장한다.

19.2 알고리즘 시뮬레이션

알고리즘의 동작을 손으로 시뮬레이션해 보는 것이 이해에 도움이 된다. 단계별로 변수의 변화를 추적한다.

19.3 구현 실습

실제 코드로 알고리즘을 구현해 보는 것이 가장 효과적인 학습 방법이다. Python, C++ 등의 언어로 구현해 본다.

20. 본 절의 의의

본 절은 그래프 이론의 기초를 다루며, 후속 절에서 다루는 다양한 알고리즘과 응용의 기반이 된다. 그래프의 정의, 종류, 표현 방법, 기본 용어를 명확히 이해하는 것이 중요하다.

21. 참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.

version: 1.0