수학에서 graph는 $G = (\mathcal{V}, \mathcal{U})$로 표현되는 쌍으로 정의되며, $\mathcal{V}$와 $\mathcal{U}$는 각각 node (또는 vertex)와 edge의 집합이다. 최근 데이터과학이나 머신러닝에서는 각 node와 edge에 대한 속성을 나타내는 node-feature 행렬 $\textbf{X}$와 edge-feature 행렬 $\textbf{E}$를 추가한 attributed graph $G = (\mathcal{V}, \mathcal{U}, \textbf{X}, \textbf{E})$를 다루기도 한다. 그러나 고전적인 그래프 이론에서는 일반적으로 속성 행렬을 고려하지 않기 때문에 특정한 언급이 없다면, 속성 행렬이 없는 일반적인 graph $G = (\mathcal{V}, \mathcal{U})$를 생각하면 된다. [그림 1]은 세 종류의 예제 graph를 시각적으로 표현한 것이다.
그래프 이론 (Graph theory)는 graph로 표현되는 것들에 대한 속성을 연구하는 수학의 한 분야이다. 그래프 이론의 내용은 물리, 화학, 컴퓨터과학 등의 다양한 분야에서도 활용되기 때문에 graph에 대한 다양한 속성을 이해하는 것이 필요하다.
Graph는 [그림 1]에서 볼 수 있듯이 node뿐만 아니라 node 간의 연결 상태를 나타내는 edge를 같이 저장할 수 있기 때문에 두 데이터 또는 점들의 관계로 정의되는 데이터를 효과적으로 표현할 수 있다. [그림 2]는 소셜 네트워크, 분자 구조, 의사 결정 프로세스와 같이 서로 다른 분야에서 나타나는 데이터 구조 및 추상적 개념을 graph의 관점에서 시각화한 것이다. 예를 들어, (b)와 같은 분자 구조에서는 각 원자가 node로 정의되며 $\mathcal{V}$는 구성 원자의 집합이 된다. 또한 각 원자의 연결은 edge로 정의되며 $\mathcal{U}$는 원자 간 화학 결합의 집합이 된다.
[그림 2]의 예시에서 볼 수 있듯이 graph는 하나의 스칼라 또는 벡터를 넘어 데이터의 관계 등과 같은 복잡한 개념을 수학적으로 표현할 수 있기 때문에 수학, 물리, 컴퓨터과학, 수리적 최적화 분야 등에서 매우 유용하게 활용되고 있다. 최근에는 graph 구조를 학습할 수 있는 그래프 인공신경망 (graph neural network, GNN)이 개발되면서 인공지능 분야에서도 graph를 활용한 연구가 활발히 진행되고 있다.
Graph는 node의 수, 구조의 복잡도, 다른 graph와의 유사도 등과 같이 다양한 종류의 성질을 가질 수 있다. 아래는 graph의 이러한 성질들을 정의하기 위한 기본적인 개념과 관련 용어에 대한 정의이다.
- Graph의 크기: $G$가 포함하고 있는 node의 수를 graph의 order $(:= |G|)$라고 한다. Graph의 order는 graph가 유한한지 무한한지를 결정할 때 사용되기도 한다.
- 두 node의 연결: 두 node $v_i$와 $v_j$에 대해 $(v_i, v_j)$가 $\mathcal{E}$에 존재하면, 즉 $(v_i, v_j) \in \mathcal{E}$인 경우 $v_i$와 $v_j$는 연결되었다고 한다. 또한 $v_i$와 $v_j$는 각각 서로의 이웃 (neighborhood)이 된다.
- Complete graph: 모든 $v_i$와 $v_j$ 쌍에 대해 edge가 존재하면, $G$는 complete하다. $n$개의 node를 포함하는 graph가 complete이면, 이를 $K^n$으로 표기한다.
- Independence: Graph에서 node의 경우, $v_i, v_j \in \mathcal{V}$ 사이에 edge가 없다면 $v_i$와 $v_j$는 independent이다. 또한 edge의 경우에는 $u_i, u_j \in \mathcal{U}$ 사이에 공유되는 node가 없다면 $u_i$와 $u_j$는 independent이다.
- Graph isomorphism (Graph 동형): 두 graph $G = (\mathcal{V}, \mathcal{U})$와 $G^{'} = (\mathcal{V}^{'}, \mathcal{U}^{'})$에 대한 모든 $v_i, v_j \in \mathcal{V}$에 대해 $(v_i, v_j) \in \mathcal{V} \Leftrightarrow (\phi(v_i), \phi(v_j)) \in \mathcal{V}^{'}$를 만족하는 $\phi: \mathcal{V} \rightarrow \mathcal{V}^{'}$가 존재하면, 두 graph $G$와 $G^{'}$는 동형 (isomorphic)이라고 한다 (그림 3).
- Subgraph: $\mathcal{V} \in \mathcal{V}^{'}$이고, $\mathcal{U}^{'} \in \mathcal{U}$이면 $G^{'}$는 $G$의 subgraph라고 한다. 만약 $G^{'}$가 $G$의 subgraph이면서 $G^{'} \neq G$이면, $G^{'}$는 $G$의 proper subgraph라고 한다.
- Induced subgraph: $G$의 subgraph $G^{'}$가 주어졌을 때, 모든 $v_i, v_j \in \mathcal{V}^{'}$가 $(v_i, v_j) \in \mathcal{U}$를 만족하면 $G^{'}$는 $G$의 induced subgraph라고 한다.
- Spanning subgraph: $G$의 subgraph $G^{'}$에 대해 $V^{'} = V$이면, $G^{'}$는 $G$의 spanning subgraph라고 한다.
- Complement $\overline{G}$: $\overline{G} = (\mathcal{V}, \mathcal{V}^2 \setminus E)$를 $G$의 complement라고 한다.
- Line graph $L(G)$: $G = (\mathcal{V}, \mathcal{U})$에 대해 $u \in \mathcal{U}$가 node가 되고, 공통된 node를 공유하는 edge가 있는 경우에는 edge에서 변환된 node가 연결되어 만들어지는 것을 $G$의 line graph $L(G)$라고 한다 (그림 4).
- Node의 degree: 어떠한 node $v$의 degree $d(v)$는 $v$가 포함된 edge의 수 $|\mathcal{U}(v)|$로 나타내며, 이는 $v$의 인접 node의 수와 같다.
- 최소 및 최대 degree: 어떠한 graph $G$에서 최소 및 최대 degree는 각각 $\delta(G) := \min\{d(v) | v \in \mathcal{V}\}$와 $\Delta(G) := \max\{d(v) | v \in \mathcal{V}\}$로 정의된다.
- Edge의 비율: Graph $G$에서 edge의 수를 node의 수로 나눈 것을 $\epsilon(G) := \frac{|\mathcal{U}|}{|\mathcal{V}|}$로 정의한다.
- Regular graph: $G$에 속한 모든 노드의 degree가 같으면 $G$를 regular graph라고 하며, degree의 값인 $k$에 따라 $k$-regular graph라고 한다.
- 홀수 degree를 갖는 node의 수: 아래의 Proof 1에 따라 그래프에서 degree가 홀수인 node의 수는 항상 짝수이다.
Graph에서 path $P = (\mathcal{V}, \mathcal{U})$로 정의되는 또 다른 그래프로 표현되며, 이 때 $\mathcal{V} = \{v_0, v_1, ..., v_K\}$에 대해 $\mathcal{U} = \{(v_0, v_1), (v_1, v_2), ..., (v_{K-1}, v_{K})\}$이다. Path를 간단하게 $P = v_0v_1 \cdots v_K$로 나타내기도 하며, $P$를 $v_0$에서 $v_K$로의 path라고 한다. 3개 이상의 node를 포함 $(K \geq 2)$하는 path $P = v_0v_1 \cdots v_K$에 대해 시작과 끝 node가 같을 경우 $(v_0 = v_K)$ 이를 cycle $C = v_0v_1 \cdots v_{K-1}v_0$이라 한다. 아래는 path와 cycle에 관한 기본 개념과 성질을 정리한 것이다.
- Path와 cycle의 길이: Path와 cycle의 길이는 포함된 edge의 수로 정의되며, 길이가 $k$인 path 또는 cycle을 각각 $P^k$와 $C^k$로 표기한다.
- A-B path: Node의 집합인 $A$와 $B$에 대해 $\mathcal{V}(P) \cap A = \{v_o\}$ 이고 $\mathcal{V}(P) \cap B = \{v_K\}$인 path $P = v_o \cdots v_K$를 A-B path라고 한다.
- Girth: Graph $G$에 포함된 모든 cycle 중에 길이가 가장 작은 것을 girth라고 하며, $g(G)$로 나타낸다.
- Chord: Graph $G = (\mathcal{V}, \mathcal{U})$의 cycle $C = (\mathcal{V}(C), \mathcal{U}(C))$에 대하여, $u \in \mathcal{U}, u \notin \mathcal{U}(C)$이면서 $C$에 포함된 두 node를 연결하는 것을 chord라고 한다. 그림 5는 chord에 대한 한 예시를 보여준다.
- 경로의 존재 가능성: 모든 graph는 길이가 $\delta(G)$인 path와 길이가 최소 $\delta(G) + 1$인 cycle을 갖는다.
- Node의 거리: Graph $G$의 두 node $v_i$와 $v_j$에 대해 최단 $v_i$-$v_j$ path의 거리를 $v_i$와 $v_j$의 거리 $d(v_i, v_j)$라고 한다.
- Graph의 지름: 어떠한 두 node의 최대 거리를 graph의 지름 (diameter)라고 한다.
- Walk: $u_i$를 $v_i$와 $v_{i+1}$ 사이의 edge라고 할 때, $v_0u_0v_1u_1 \cdots u_{k-1}v_k$를 길이가 $k$인 walk라고 한다. 만약 $v_0 = v_k$이면 walk는 닫혀있다고 한다 (closed walk).
- Connected graph: 어떠한 두 node를 연결하는 path가 항상 존재하면 graph는 연결되었다고 한다.
- Component: graph $G$의 subgraph 중에서 가장 큰 connected subgraph를 $G$의 component라고 한다.