📂그래프이론

그래프의 행렬 표현

정의 ¹

그래프 $G(V,E)$가 주어졌다고 하자.

차수 행렬

각 버텍스 $v_{i}\in V$ 의 차수 $d(v_{i})$를 간단히 $d_{i}$라고 표기하자. 다음과 같은 행렬을 $G$ 의 차수 행렬^{degree matrix}이라고 하고 $D(G)$ 혹은 간단하게 $D$라고 표기한다.

$$D(G) = \mathrm{diag} (d_{1}, \dots, d_{n}) = \begin{bmatrix} d_{1} & 0 & \cdots & 0 \\ 0 & d_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{n} \end{bmatrix}$$

이때 $\mathrm{diag}$ 는 대각행렬이다.

인접 행렬

다음과 같은 정사각행렬을 $G$ 의 인접 행렬^{adjacent matrix}이라고 하고 $A(G)$ 혹은 간단하게 $A$라고 표기한다.

$$A = [a_{ij}] = \begin{cases} 1 &, ij \in E(G) \\ 0 &,ij \notin E(G) \end{cases}$$

인접 행렬은 이산적으로도 풍부한 성질을 가지면서 행렬의 꼴을 하고 있기 때문에 선형 대수의 여러가지 이론을 접목시킬 수 있다. 특히 그 고유값은 네트워크를 응용하는 여러 모델에서 자주 언급된다.

근접 행렬

다음과 같은 행렬을 $G$ 의 근접 행렬^{incident matrix}이라고 하고 $M(G)$ 혹은 간단하게 $M$이라고 표기한다.

$$M = [m_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is incident with edge } j \\ 0 &, \text{otherwise} \end{cases}$$

유향 근접 행렬

$G$가 유향 그래프라고 하자. 다음과 같은 행렬을 $G$ 의 유향 근접 행렬^{directed incident matrix}이라고 하고 $N(G)$ 혹은 간단하게 $N$이라고 표기한다.

$$N = [n_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is tail of edge } j \\ -1 &, \text{vertex } i \text{ is head of edge } j \\ 0 &, \text{otherwise} \end{cases}$$

예시

가령 위와 같은 그래프에 대해서 다음과 같은 행렬을 얻는다.

$$D = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$

$$A = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{3} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{4} & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ v_{5} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{7} & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$

$$M = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$

위와 같은 유향 그래프에 대한 유향 근접 행렬은 다음과 같다.

$$N = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$