[Discrete Mathematics] 그래프(graph)의 기본 개념과 그래프 구분

---

그래프

 

그래프는 정점(vertex)과 간선(edge)로 이루어져 있는데, 각 정점들을 연결하는 것이 간선이다. 특정 정점에서 다른 정점으로 이동하는것을 경로(path)라 한다.

그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 나눌 수 있는데, 무방향 그래프는 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있고, 각 간선 $ e \in E $ 는 순서가 없는 정점의 쌍으로 나타낸다. 일반적으로 그냥 그래프라 말하면 무방향 그래프를 말한다. 방향 그래프 역시 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있는데, 각 간선 $ e \in E $ 는 순서가 있는 정점의 쌍으로 나타낸다. 통합적으로 그래프 $ G $ 는 $ G = ( V, E ) $ 로 나타낸다.

그래프의 $ v_0, v_n \in V $ 에 대하여 $ v_0 $ 에서 $ v_n $ 까지의 길이가 $ n $ 인 경로는 $ v_0 $ 에서 시작하여 $ v_n $ 으로 끝나면서 $ n +1 $ 개의 정점과 $ n $ 개의 간선이 교차하는 순서열로 $ ( v_0 , e_1, v_1, e_2, \cdots , v_{n-1}, e_n, v_n ) $ 과 같이 나타낸다. 이때 $ e_i $ $(i = 1, 2, \cdots, n)$ 는 $ v_{i-1} $ 와 $ v_i $ 에 결합되어 있어야 한다. 단 병렬 간선이 없을 때는 간선없이 정점만으로 표현 가능하다.

어떤 그래프 $ G $ 를 구성하는 정점 집합과 간선 집합이 있을 때, 해당 정점 집합의 부분 집합으로 이루어진 집합을 정점 집합으로, 해당 간선 집합의 부분 집합으로 이루어진 집합을 간선 집합으로 하는 다른 그래프  $ G^\prime $ 이 존재한다면 $ G^\prime $ 을 $ G $ 의 부분 그래프라 한다.

어떤 그래프 $ G = (V, E) $ 에 대하여 $ v \in V $ 를 가정할 때 $ v $ 시작되는 어떤 경로에 포함된 $ G $ 안에 모든 간선과 정점으로 구성된 $ G $ 의 부분 그래프 $ G^\prime $ 을 $ v $ 를 포함하는 $ G $ 의 요소(component)라 한다. 그래프가 연결 그래프일 필요충분조건은 그래프가 정확히 하나의 요소를 가지는 것이다.

경로에 대해 알아보면, 어떤 그래프 $ G = ( V, E ) $ 에 대하여 $ v, w \in V $ 를 가정하자. $ v $ 에서 $ w $ 까지 반복되는 정점이 없는 경로가 있다면 이를 단순 경로(simple path)라 한다. $ v $ 에서 $ v $ 까지 반복되는 간선없이 길이가 $ 0 $이 아닌 경로는 사이클(cycle) 혹은 회로(circuit)라 한다. 단순 사이클(simple cycle)은 시작과 끝을 제외하고는 반복되는 정점이 없는 사이클이다.

어떤 정점 $ v $ 의 결합된 간선의 수를 차수(degree)라 하고 $ \delta (v) $ 로 나타낸다. 루프는 차수에 $2$를 기여한다.

 

---

그래프 구분

 

그림으로 그래프를 그린다면 각 정점을 그리고 간선을 잇는데, 무방향 그래프는 실선으로, 방향 그래프는 화살표로 간선을 그림으로써 구별 가능하다. 아래 그림 중 왼쪽이 무방향 그래프, 오른쪽이 방향 그래프이다.

어떤 그래프에서 정점의 쌍 $ v $ 와 $ w $ 를 잇는 간선 $ e $ 이 있다면 이 간선 $ e $ 는 $ v $ 와 $ w $ 에 결합된다(incident on)고 하고, 역시 정점 $ v $ 와 $ w $ 는 간선 $ e $ 에 결합된다고 한다. 이때 $ v $ 와 $ w $ 를 인접 정점(adjacent vertex)이라 한다.

만약 같은 정점의 쌍에 둘 이상의 간선이 결합되어 있다면 이 간선들을 병렬 간선(parallel edge)이라 한다. 하나의 정점에 결합된 간선, 즉 어떤 정점에서 그 정점으로 가는 간선을 루프(loop)라 한다. 고립 정점(isolated vertex)은 어떠한 간선도 결합되지 않은 정점이다. 만약 루프도, 병렬 간선도 가지지 않는다면 단순 그래프(simple graph)라 한다. 아래 그림에서 $ e_1, e_2 $ 가 병렬 간선이고, $ e_3 $ 가 루프이며, $ v_6 $ 이 고립 정점이다. 아래 그림에서 $ v_3, v_4, v_5 $ 와 $ e_4, e_5, e_6 $ 로 이루어진 부분 그래프는 루프도 병렬 간선도 없기 때문에 단순 그래프이다.

완전 그래프(complete garph)는 모든 정점들 간에 간선이 존재하는 그래프로 $ n $ 개의 정점을 가지는 단순 그래프이며, 이를 $ K_n $ 으로 표기한다. 아래 그래프가 완전 그래프이다.

이분 그래프(bipartite graph)는 $ V_1, V_2 \subset V $ 가 $ V_1 \cap V_2 = \emptyset $ 이고 $ V_1 \cup V_2 = V $ 를 만족하면서, 모든 $  e \in E $ 가 $ e = (v_1, v_2) $ 이고 $ v_1 \in V_1 $ 과 $ v_2 \in V_2) $ 를 만족하는 그래프이다. 아래 그래프가 이분 그래프이다.

완전 이분 그래프(complete bipartite graph)는 $ m $ 개의 정점을 가지는 집합 $ V_1 $ 과 $ n $ 개의 정점을 가지는 집합 $ V_2 $ 로 분할되는 이분 그래프로 서로 다른 집합에 속하는 정점이 모두 연결되어 있는, 즉 간선의 집합 $ E $ 가 $ E = \{ (v_1, v_2) \mid v_1 \in V_1, v_2 \in V_2 \} $ 인 그래프이다. 이는 단순 그래프이며 $ K_{m,n} $ 으로 나타낸다. 아래 그래프가 완전 이분 그래프이다.

그래프의 $ v, w \in V $ $ ( v \neq w ) $ 를 가정할 때 모든 $ v $ 와 $ w $ 사이 경로가 존재한다면 그래프가 연결되어 있다고 말하고, 이 그래프를 연결 그래프(connected graph)라 한다. 반대로 하나다로 경로가 없는 서로 다른 정점이 있다면 비연결 그래프(unconnected graph)라 한다. 아래 그래프에서 왼쪽이 연결 그래프, 오른쪽이 비연결 그래프이다.

 

---

그래프 표현

 

그래프를 위 그림들처럼 표현할 수도 있지만, 컴퓨터에서 처리하기 위해서는 다른 방식으로 표현해야 한다.

대표적인 방법 중 하나가 인접행렬(adjacency matrix)로 표현하는 방법이다. 각 정점들의 순서를 정한 후 순서가 정해진 정점들을 행렬의 가로와 세로에 표기한다. 그 후 행렬의 값에는 그 열에 표기된 정점과 행에 표기된 정점이 간선으로 연결되어 있으면 1을 연결되어 있지 않으면 0을 표기한다. 만약 루프가 있다면 2로 표기한다.

위 그래프를 인접행렬로 표현하면 다음과 같다.

$$ \begin{matrix} \begin{array}{c|ccccc} & v_1 & v_2 & v_3 & v_4 & v_5 \\ \hline v_1 & 0 & 0 & 0 & 0 & 1 \\ v_2 & 0 & 0 & 1 & 0 & 1 \\ v_3 & 0 & 1 & 0 & 1 & 1 \\ v_4 & 0 & 0 & 1 & 0 & 1 \\ v_5 & 1 & 1 & 1 & 1 & 0 \end{array} \end{matrix} $$

그래프 $ G $ 안의 정점 $ v $ 의 차수는 $ G $ 의 인접행렬에서 $ v $ 의 행이나 열을 더하여 얻을 수 있다. 즉 인접행렬로 표현하면 정점의 차수를 구할 때 이점이 있다. 그러나 인접행렬로 표현하면 무방향 그래프인 경우 주 대각선에 대하여 대칭이므로 정보가 대각선을 제외하고 두 번 나타나게 되어 메모리 공간의 손실이 발생한다.

또 다르게 결합행렬(incidence matrix)을 통해 각 정점을 행에, 간선을 열에 표시하여, 간선이 어떤 정점을 연결하는가를 나타내어 그래프를 표현할 수도 있다. 어떤 간선 $ e_1 $ 가 $ v_1 $ 과 $ v_2 $ 를 연결한다면 $ e_1 $ 의 열에 $ v_1, v_2 $ 행의 값을 1로, 나머지 행의 값을 0으로 표기한다. 만약 $ e_2 $ 이 $ v_3 $ 의 루프라면 $ e_2 $ 열은 $ v_3 $ 행만 1로 표기한다. 각 행의 합은 그 행에 명시된 정점의 차수를 나타낸다.

위 그래프를 결합행렬로 나타내면 다음과 같다.

$$ \begin{matrix} \begin{array}{c|cccccc} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 \\ \hline v_1 & 0 & 0 & 0 & 1 & 0 & 0 \\ v_2 & 1 & 0 & 0 & 0 & 1 & 0 \\ v_3 & 1 & 1 & 0 & 0 & 0 & 1 \\ v_4 & 0 & 1 & 1 & 0 & 0 & 0 \\ v_5 & 0 & 0 & 1 & 1 & 1 & 1 \end{array} \end{matrix} $$