[이산 수학] 그래프의 개념

그래프의 개념

• 점과 선을 이용해 개념, 구조 또는 과정 등을 이해하는 데 필요한 주요 요소 간의 관계, 거리, 비용 등을 시각적으로 표현한 도구를 그래프(Graph)라고 한다.
• 그래프는 글이나 수식으로는 복잡하고 어렵게 표현되는 것을 그림으로 표현하기 때문에 컴퓨터 시스템의 회로나 네트워크 설계나 구조, 프로그램의 알고리즘, 인공지능의 지식 정보의 파생 과정 및 내용 등을 표현하는 데 효율적이고 효과적으로 활용된다.
• 그래프는 정점과 변으로 표현되기 때문에 정점에 대한 정보와 변에 대한 정보를 정의함으로써 그래프를 정의하고 표현한다. 
• 그래프는 보통 그림 형태로 표현하지만, 집합 표현과 같은 수학적 기호로 표현할 수도 있다.

 

그래프의 정의와 표현

그래프(Graph : $G = (V, \; E)$ )

공집합이 아닌 정점(Vertex, Node)의 집합 `V` 와 서로 다른 정점의 쌍 $(v_{i}, \; v_{j})$ 를 연결하는 변(Edge)의 집합 `E` 로 구성된 구조

$$G = (V, \; E) \\ V = \{v_{1}, v_{2}, \cdots, v_{n} \} \\ E = \{e_{1}, e_{2}, \cdots, \;e_{m} \} = \{(v_{i}, v_{j}), \cdots \}, \quad 1 \le i, \; j \le n$$

- 정점 $v_{i}$ 와 $v_{j}$ 는 서로 인접(Adjacent)한다 : 정점 $v_{i}$ 와 $v_{j}$ 를 연결하는 변이 존재한다.
- 변 $e_{k}$ 는 정점 $v_{i}$ 와 $v_{j}$ 에 근접(Incident)한다 : 변 $e_{k}$ 는 정점 $v_{i}$ 와 $v_{j}$ 를 연결한다.

• 위의 정의에서 사용한 기호 표현의 의미는 다음과 같다.

- $G = (V, \; E)$ : 정점의 집합 `V` 와 변이 집합 `E` 로 구성되는 그래프 `G` - $V = \{v_{1}, v_{2}, \cdots, v_{n} \}$ : 그래프 `G` 를 구성하는 정점의 집합 `V` - $E = \{e_{1}, e_{2}, \cdots, \;e_{m} \}$ : 그래프 `G` 를 구성하는 변의 집합 `E`         $= \{(v_{i}, v_{j}), \cdots \}$ : 변의 집합 `E` 와 각 원소가 근접하는 정점의 쌍

• 그래프를 구성하는 각 변에 변의 이름 또는 번호를 부여한다면 $E = \{e_{1}, e_{2}, \cdots, \;e_{m} \}$ 처럼 변의 이름이나 번호를 집합의 원소로 사용할 수 있고, 변에 근접하는 정점의 쌍 $(v_{i}, v_{j})$ 를 변의 집합의 원소로 사용하기도 한다.
• 변의 방향성이 없는 경우, 정점의 쌍 $(v_{1}, v_{2})$ 와 $(v_{2}, v_{1})$ 이 같은 변에 대한 표현이므로 같은 원소로 취급한다.
• 반면, 변의 방향성이 있는 경우에는 방향 그래프처럼 정점의 쌍이 화살표의 시작과 끝의 의미를 포함하는 순서쌍의 의미를 갖는다.
  • 이 때, 정점의 쌍과 순서쌍을 구분하기 위해 $( \; )$ 대신 $< \; >$ 형태의 괄호를 사용한다.

방향성이 있는 변의 순서쌍 표현. (a)와 (b)는 전혀 다른 변이다.

 

'정점의 쌍'과 '순서쌍'의 구분

• 순서쌍 `(a, b)` 는 순서쌍을 구성하는 원소 `a` 와 `b` 사이에 순서가 존재함을 보여주는 원소 표현 방법 중 하나이다.
• 그러나 일반적인 그래프에서 정점 `a` 와 `b` 에 근접하는 변을 표현하는 정점의 쌍 `(a, b)` 는 순서쌍 `(a, b)` 와 달리 정점 `a` 와 `b` 사이의 순서에 의미가 없다.
• 그러므로 그래프에서 사용하는 `(a, b)` 에는 '순서쌍' 이 아닌 '정점의 쌍' 이라는 용어를 사용한다.
• 단, 그래프의 정점 `a` 와 `b` 사이에 순서가 존재하여 `<a, b>` 로 표기하는 경우에는 '정점의 순서쌍' 이라는 용어를 사용한다.

 

루프(Loop)

루프의 표현

• (a)와 같은 변을 루프(Loop)라고 하는데, 루프는 하나의 정점에만 인접하는 변으로 (b)와 같이 펼쳐서 이해해도 된다.

 

예 : 다음의 그래프를 수학적 기호로 표현하라.

• 필요한 정보를 정리하면 다음과 같다.
  • 그래프 `G` 는 정점의 집합 `V` 와 변의 집합 `E` 로 구성된다.
  • 집합 `V` 는 정점 $v_{1}, v_{2}, v_{3}, v_{4}$ 로 구성된다.
  • 집합 `E` 는 변 $e_{1}, e_{2}, e_{3}$ 로 구성되며, 각 변에 대한 정점의 쌍은 다음과 같다.
    • $e_{1} = (v_{1}, v_{2})$ 또는 $(v_{2}, v_{1})$
    • $e_{2} = (v_{1}, v_{3})$ 또는 $(v_{3}, v_{1})$
    • $e_{3} = (v_{3}, v_{3})$ 
• 앞과 같이 정리한 내용을 이용해 다음과 같이 표현할 수 있다.

$$G = (V, \; E) \\ V = \{v_{1}, v_{2}, v_{3}, v_{4} \} \\ E = \{ e_{1}, e_{2}, e_{3} \} = \{ (v_{1}, v_{2}), (v_{1}, v_{3}), (v_{3}, v_{3}) \} = \{ (v_{2}, v_{1}), (v_{3}, v_{1}), (v_{3}, v_{3}) \}$$

• 그래프의 수학적 기호 표현을 이용해 다시 그래프로 표현할 때 원래의 그래프와 같은 그래프가 나와야 한다.
• 위 그래프에서 정점 $v_{4}$ 의 경우, 다른 정점과 연결되는 변이 존재하지 않아서 정점의 쌍이 없지만, 정점 집합에는 포함되므로 그래프로 표현할 때에도 반드시 표시해야 한다.

 

그래프의 형태

단순 그래프(Simple Graph)

그래프 $G = (V, \; E)$ 에서 임의의 두 정점 사이에 오직 하나의 변이 있는 그래프

 

다중 그래프(Multi-Graph)

그래프 $G = (V, \; E)$ 에서 임의의 두 정점 사이에 2개 이상의 변이 있는 그래프

• 다중 그래프는 두 정점 사이에 여러 개의 변이 존재하므로, 수학적 기호로 표기할 때 같은 정점의 쌍을 변의 개수 만큼 표시해야 한다.
• 위의 정의에 주어진 다중 그래프를 수학적 기호로 표기하면 다음과 같다.

$$G = (V, E) \\ V = \{ a, b \} \\ E = \{(a, b), (a, b), (a, b) \}$$

 

다중 그래프의 변에 대한 집합 표기

• 집합은 '중복되지 않는 원소의 모임'이라고 정의된다.
• 그래프의 표기에서도 이와 같은 정의를 따라야 하지만, 다중 그래프의 경우 두 정점에 근접하는 변들을 모두 표기해야 하므로 집합의 정의에 위배될 수 밖에 없다.

 

방향 그래프(Directed Graph : $G = <V, \; E>$ )

그래프를 구성하는 정점 사이에 순서가 존재하여 화살표를 이용해 순서대로 정점을 연결하여 표현하는 그래프

$$G = <V, \; E> \\ V = \{v_{1}, v_{2}, \cdots, v_{n} \} \\ E = \{e_{1}, e_{2}, \cdots, \;e_{m} \} = \{<v_{i}, v_{j}>, \cdots \}, \quad 1 \le i, \; j \le n$$

• 일반적인 그래프와 달리 방향 그래프는 인접하는 정점 사이에 순서가 있어서 시작하는 정점에서 끝나는 정점의 방향으로 화살표를 실선 대신 표시한다.
• 두 표기 $(v_{i}, v_{j})$ 와 $(v_{j}, v_{i})$ 를 같은 변으로 취급하는 일반 그래프와 달리, 방향 그래프는 $< >$ 를 이용하여 $<v_{i}, v_{j}>$ 나 $<v_{j}, v_{i}>$ 로 나타내어 두 표기를 전혀 다른 변으로 취급한다.
• 위의 정의에 주어진 방향 그래프를 수학적 표기로 표현하면 다음과 같다.

$$G = <V, \; E> \\ V = \{v_{1}, v_{2}, v_{3}, v_{4} \} \\ E = \{<v_{1}, v_{1}>, <v_{1}, v_{2}>, <v_{2}, v_{1}>, <v_{2}, v_{3}>,  <v_{3}, v_{4}>, <v_{4}, v_{3}>, <v_{4}, v_{4}> \}$$

 

가중치 그래프(Weighted Graph)

그래프 $G = (V, \; E)$ 를 구성하는 각 변에 가중치가 부여된 그래프
- $W[v_{i}, \; v_{j}]$ : 두 정점 $v_{i}$ 와 $v_{j}$ 에 근접하는 변에 부여된 가중치 표기

• 도로망이나 네트워크를 설계하거나 평가할 때 각 연결선에 교통량이나 통신량 등을 표시하기도 하는데, 이 교통량 또는 통신량이 각 연결선에 대한 가중치의 의미를 갖는다.
• 이처럼 가중치 그래프는 그래프를 평가하는 데 사용할 수 있다.
• 각 변에 부여된 가중치는 $W[v_{i}, \; v_{j}] = m$ 과 같이 나타내는데, 위의 정의에 주어진 가중치 그래프에서 각 변의 가중치를 표기하면 다음과 같다.

$W[v_{1}, \; v_{2}] = 3, \quad W[v_{1}, \; v_{2}] = 7, \quad W[v_{2}, \; v_{3}] = 6, \quad W[v_{3}, \; v_{3}] = 8$

 

그래프의 차수

• 그래프는 정점과 변으로 구성된다.
• 그러므로 각 정점에 근접하는 변의 개수는 그래프에 대한 다양한 판단을 하는 주요 기준이 된다.

 

차수(Degree : $d(v)$ )

정점 `v` 에 근접하는 변의 개수

방향 그래프에 대하여,
① 외차수(Out-Degree : $d_{\text{out}}(v)$) : 정점 `v` 를 시작점으로 하는 화살표의 개수 / 진출 차수
② 내차수(In-Degree : $d_{\text{in}}(v)$) : 정점 `v` 를 끝점으로 하는 화살표의 개수 / 진입 차수

 

예 : 무방향 그래프

• 아래 그래프를 구성하는 각 정점의 차수를 구해보자.
• (b)는 (a) 그래프를 분해하여 2개의 그래프로 표현한 것이다.

그래프의 차수

• (b1)은 두 정점 $v_{1}, v_{2}$ 에 근접하는 변으로 다음과 같이 각 정점에 대한 차수를 구할 수 있다.

$$d(v_{1}) = 1, \quad d(v_{2}) = 1$$

• (b2)는 정점 $v_{2}$ 에 대한 루프로 다음과 같이 왼쪽에 위치한 정점 $v_{2}$ 의 차수와 오른쪽에 위치한 정점 $v_{2}$ 의 차수를 별도로 구할 수 있다.

$$d(v_{2}) = 1, \quad d(v_{2}) = 1$$

• 결과적으로 (b1)과 (b2)를 이용하여 구한 (a) 그래프의 각 정점의 차수를 정리하면 다음과 같다.

$$d(v_{1}) = 1, \quad d(v_{2}) = 3$$

 

예 : 방향 그래프

• 방향 그래프의 경우에는 정점에서 시작하는 화살표 개수와 정점에서 끝나는 화살표 개수를 구분하여 구한다.

방향 그래프의 차수

• 정점 `a` 의 경우, 정점 `a` 를 끝점으로 하는 화살표만 존재하므로 정점 `a` 의 외차수와 내차수는 다음과 같다.

$$d_{\text{out}}(a) = 0, \quad d_{\text{in}}(a) = 1$$

• 정점 `b` 의 경우, 루프 화살표가 존재하는데, 이 때 정점 `b` 에서 시작하는 화살표 하나, 정점 `b` 로 끝나는 화살표 하나로 볼 수 있다.
• 그러므로 정점 `b` 의 외차수와 내차수는 다음과 같다.

$$d_{\text{out}}(b) = 1, \quad d_{\text{in}}(b) = 1$$

• 정점 `c` 의 경우 ,정점 `c` 에서 시작하는 화살표(정점 `d` 가 끝점), 정점 `c` 로 끝나는 화살표(정점 `d` 가 시작점)가 존재한다.
• 따라서 정점 `c` 의 외차수와 내차수는 다음과 같다.

$$d_{\text{out}}(c) = 1, \quad d_{\text{in}}(c) = 1$$

• 정점 `d` 의 경우 ,정점 `d` 에서 시작하는 화살표(정점 `a` 와 `c` 가 끝점) 2개와 정점 `d` 로 끝나는 화살표(정점 `c` 가 시작점) 1개가 존재한다.
• 따라서 정점 `d` 의 외차수와 내차수는 다음과 같다.

$$d_{\text{out}}(d) = 2, \quad d_{\text{in}}(d) = 1$$

 

차수에 대한 정리

• 다음은 그래프를 구성하는 정점의 차수에 대해 항상 성립하는 정리이다.

① 그래프 $G = (V, \; E)$ 에서 모든 정점의 차수의 합은 변의 개수의 2배이다.

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

② 그래프 $G = (V, \; E)$ 에서 차수가 홀수인 정점의 개수는 짝수이다.

 

증명

① 증명

• 그래프에서 변 `e` 는 항상 2개의 정점 `u, v` 에 근접한다.
• 그러므로 변 `e` 는 정점 `u` 의 차수를 구할 때와 정점 `v` 의 차수를 구할 때 두 번 계산된다.
• ∴ 하나의 변은 정점 2개의 차수를 계산하는 데 항상 중복되므로, 모든 정점의 차수의 합은 변의 개수의 2배이다.

 

② 증명

• 그래프 $G = (V, \; E)$ 에서 차수가 짝수인 정점의 집합이 $V_{e}$, 차수가 홀수인 정점의 집합이 $V_{o}$ 일 때, ①에 의해 그래프의 변의 개수는 다음과 같이 구할 수 있다.

$$2|E| = \sum_{v \in V} d(v) = \sum_{v \in V_{e}}d(v) + \sum_{v \in V_{o}}d(v)$$

• 이 때, 각 $v \in V_{e}$ 에 대하여 $d(v)$ 가 짝수이므로 $\displaystyle \sum_{v \in V_{e}} d(v)$ 는 짝수이다.

$$\sum_{v \in V_{e}} d(v) = 2k \; (k \in N)$$

• 위의 두 번째 식을 이용하여 첫 번째 식을 다시 작성하면 다음과 같다.

$$2|E| = \sum_{v \in V} d(v) = \sum_{v \in V_{e}} d(v) + \sum_{v \in V_{o}} d(v) = 2k + \sum_{v \in V_{o}} d(v)$$

• 따라서 $\displaystyle \sum_{v \in V_{o}} d(v) = 2|E| - 2k = 2(|E| - k)$ 이므로 $\displaystyle \sum_{v \in V_{o}} d(v)$ 도 짝수이다.
• 그런데 각 $v \in V_{o}$ 에 대하여 $d(v)$ 가 홀수이므로 $\displaystyle \sum_{v \in V_{o}} d(v)$ 가 짝수이려면 집합 $V_{o}$ 의 기수($|V_{o}|$), 즉 집합 $V_{o}$ 에 포함된 정점의 개수가 짝수여야 한다.
• 그러므로 차수가 홀수인 정점의 개수는 짝수이다.

 

예 : 차수에 대한 정리 확인하기

• 이 그래프를 구성하는 각 정점의 차수는 다음과 같고, 차수가 홀수인 정점의 수는 2개로 짝수 개임을 알 수 있다.

$$d(v_{1}) = 2, \quad d(v_{2}) = 1, \quad d(v_{3}) = 3, \quad d(v_{4}) = 0$$

• 또한 이 그래프의 변의 개수는 $|E| = 3$ 이다.
• 정리 ①의 식에 이 값들을 대입하면 그래프의 모든 정점의 차수의 합은 변의 개수의 2배임을 알 수 있다.

$$\sum_{v \in V} d(v) = d(v_{1}) + d(v_{2}) + d(v_{3}) + d(v_{4}) = 2 + 1 + 3 + 0 = 6 = 2 \times 3 = 2|E|$$

• 여기서 이 그래프의 각 정점 중 홀수 차수인 정점은 $v_{2}$ 와 $v_{3}$ 2개로, 차수가 홀수인 정점은 짝수 개이다.
• 따라서 그래프를 구성하는 정점의 차수의 합은 항상 짝수이고, 홀수 차수인 정점은 짝수 개임을 확인하였다.
• 따라서 정점이나 변에 대한 정보가 주어진다고 해서 무조건 그래프인 것이 아니므로, 차수에 대한 정리를 이용해 그래프인지를 먼저 판별하는 과정이 필요할 수 있음을 기억해야 한다.