◀️ 🌱 April 🌱 ▶️
일	월	목	금	토
		0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0

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

2022. 11. 25. 21:07

728x90

그래프의 개념

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

그래프의 정의와 표현

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

공집합이 아닌 정점(Vertex, Node)의 집합 $V$ 와 서로 다른 정점의 쌍 $(v_{i}, \; v_{j})$ 를 연결하는 변(Edge)의 집합 $E$ $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)

$G = (V, \; E)$ : 정점의 집합

V

$V$ 와 변이 집합

E

$E$ 로 구성되는 그래프

G

$G$
-

V = {v_{1}, v_{2}, \dots, v_{n}}

$V = \{v_{1}, v_{2}, \cdots, v_{n} \}$ : 그래프

G

$G$ 를 구성하는 정점의 집합

V

$V$
-

E = {e_{1}, e_{2}, \dots, e_{m}}

$E = \{e_{1}, e_{2}, \cdots, \;e_{m} \}$ : 그래프

G

$G$ 를 구성하는 변의 집합

E

$E$

= {(v_{i}, v_{j}), \dots}

$= \{(v_{i}, v_{j}), \cdots \}$ : 변의 집합

E

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

루프(Loop)

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

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

필요한 정보를 정리하면 다음과 같다.
- 그래프 $G$ $G$ 는 정점의 집합 $V$ $V$ 와 변의 집합 $E$ $E$ 로 구성된다.
- 집합 $V$ 는 정점 $v_{1}, v_{2}, v_{3}, v_{4}$ 로 구성된다.
- 집합 E $E$ 는 변 e1,e2,e3 $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})}

$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)}

$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} >}

$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, W [v_{1}, v_{2}] = 7, W [v_{2}, v_{3}] = 6, W [v_{3}, v_{3}] = 8

$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$ $v$ 에 근접하는 변의 개수

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

예 : 무방향 그래프

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

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

d (v_{1}) = 1, d (v_{2}) = 1

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

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

d (v_{2}) = 1, d (v_{2}) = 1

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

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

d (v_{1}) = 1, d (v_{2}) = 3

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

예 : 방향 그래프

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

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

d_{out} (a) = 0, d_{in} (a) = 1

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

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

d_{out} (b) = 1, d_{in} (b) = 1

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

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

d_{out} (c) = 1, d_{in} (c) = 1

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

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

d_{out} (d) = 2, d_{in} (d) = 1

$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$ $e$ 는 항상 2개의 정점 $u, v$ $u, v$ 에 근접한다.
그러므로 변 $e$ $e$ 는 정점 $u$ $u$ 의 차수를 구할 때와 정점 $v$ $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)

$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) = 2 k (k \in N)

$\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) = 2 k + \sum v \in V_{o} d (v)

$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, d (v_{2}) = 1, d (v_{3}) = 3, d (v_{4}) = 0

$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 |

$\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개로, 차수가 홀수인 정점은 짝수 개이다.
따라서 그래프를 구성하는 정점의 차수의 합은 항상 짝수이고, 홀수 차수인 정점은 짝수 개임을 확인하였다.
따라서 정점이나 변에 대한 정보가 주어진다고 해서 무조건 그래프인 것이 아니므로, 차수에 대한 정리를 이용해 그래프인지를 먼저 판별하는 과정이 필요할 수 있음을 기억해야 한다.

728x90

저작자표시 비영리 변경금지

'Mathematics > 이산 수학' 카테고리의 다른 글

[이산 수학] 그래프의 활용 (0)	2022.11.27
[이산 수학] 오일러와 해밀턴 (0)	2022.11.26
[이산 수학] 그래프의 표현 (0)	2022.11.26
[이산 수학] 그래프의 종류 (0)	2022.11.25
[이산 수학] 함수의 종류 (0)	2022.11.21
[이산 수학] 합성 함수 (0)	2022.11.21
[이산 수학] 함수의 성질 (0)	2022.11.14
[이산 수학] 함수의 개념 (0)	2022.11.14

Per ardua ad astra."Hello, World!" 🤖

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Per ardua ad astra.

"Hello, W

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

그래프의 개념