📂그래프이론

수학에서의 그래프와 네트워크

정의 ¹

1. 정점과 정점들을 연결한 선들로 이루어진 집합을 그래프 혹은 네트워크라고 한다. 정점들의 집합을 $V$, 선들의 집합을 $E$라고 하자.
2. $V(G) := V$ 의 원소를 $G$ 의 버텍스^vertex 혹은 노드^node라고 한다.
3. $E(G) := E$ 의 원소를 $G$ 의 에지^edge 혹은 링크^link라고 한다.
4. 자기 자신으로 이어진 에지를 루프^loop라고 한다.
5. 두 버텍스가 에지로 이어져 있으면 인접^adjacent하다고 한다.
6. 에지에 방향이 있는 그래프를 유향 그래프^digraph라고 한다.
7. 유한한 버텍스를 가지며 두 버텍스를 잇는 에지는 하나뿐이며 루프가 존재하지 않고 유향 그래프가 아닌 그래프를 심플 그래프^{simple Graph}라고 한다.

설명

꼭 그런 것은 아니지만, 같은 개념이라도 순수수학에서는 그래프라는 말을 선호하고 응용수학에서는 네트워크라는 말을 선호하는 경향이 있다. 다만 어느 쪽이 됐든 동의어가 있고 각자 자기 분야에서는 그 영향력도 꽤 강한 편이라 섞어서 사용하지는 않는 편이다.

1. 일반적으로 말하는 그래프라는 것은 위의 그림처럼 자유분방한 모양이다.
2. 검은색 동그라미는 각각의 버텍스를 의미하며, 위치의 개념을 가지지 않는다. 순수 그래프 이론에서 그래프의 오더^order란 보통 이 버텍스 집합의 기수 $n = |V(G)|$ 를 말한다. 위 그래프의 오더는 $5$ 다.
3. 버텍스들을 잇는 에지들은 마찬가지로 그 관계만을 나타낼 뿐 모양이나 길이의 개념이 없다. 참고로 Edge는 보통 한국인이 직관적으로 생각하는 것처럼 [엗지]가 아니라 [에지]로 발음되는 게 맞다. 순수 그래프 이론에서 그래프의 사이즈Size란 보통 이 에지 집합의 기수 $m = |E(G)|$ 를 말한다. 위 그래프의 사이즈는 $8$ 이다. 그러나 응용 네트워크 이론에서 사이즈는 그냥 그래프의 오더 $|V(G)|$ 를 칭하는 경우가 많다. 이는 분야에 따른 문맥으로 구분해야한다.
4. 왼쪽 위의 버텍스는 자신과 자신을 잇는 에지를 가지고 있으며, 이러한 모양 때문에 루프라고 불린다.
5. 두 버텍스가 인접하다는 것은 에지로 이어져있다는 말로써, 역시 그 관계만 중요할 뿐 눈에 보이는 거리는 중요치 않다. 두 버텍스 $u, v$ 가 인접하면 $u \sim v$ 와 같이 나타내며, 그래프 $G$ 에서 버텍스 $v \in V(G)$ 에 인접한 버텍스를 모아놓은 집합을 $v$ 의 네이버후드 $N_{G} (v)$ 와 같이 나타내기도 한다.
6. 유향 그래프란 위의 그림처럼 에지에 방향성이 있는 그래프를 말한다. 유향 그래프에서 에지는 아크^arc라 불리기도 한다. 버텍스 $u$에서 나와 $v$로 들어가는 에지는 $u \to v$로 표기하며 $u$를 테일^tail, $v$를 헤드^head라 부른다.
7. 심플 그래프란 말은 어렵지만 쉽게 말해 루프니 멀티 에지니 디렉션이니 하는 것 없이 위의 그림처럼 깔끔한 그래프를 말한다. 보통 그래프 이론이라고 한다면 이렇듯 심플한 형태에 관심을 가지는 것이 보통이다.

어려운 정의

이러한 정의들은 그래프의 개념을 쉽게는 설명하지만 엄밀함에는 다소 문제가 있어 다음의 어려운 정의를 소개한다. 개념은 말 그대로 위에서 쉽게 정의한 것과 다르지 않으므로 수학적인 표현에만 익숙하다면 받아들이는데에 큰 어려움은 없을 것이다.

1. 집합 $V \ne \emptyset$ 와 이항관계 $\sim \subset V^2$ 에 대해 $G := \left( V, \sim \right)$ 을 그래프 혹은 네트워크라고 한다.
2. $V(G) := V$ 의 원소를 $G$ 의 버텍스 혹은 노드라고 한다.
3. $E(G) := \sim$ 의 원소를 $G$ 의 에지라 혹은 링크라고 한다.
4. $v \in V(G)$ 에 대해 $(v,v) \in E(G)$ 을 루프라고 한다.
5. $v_{1} , v_{2} \in V(G)$ 에 대해 $(v_{1} , v_{2} ) \in E(G)$ 이면 $v_{1}$ 와 $v_{2}$ 가 인접하다고 한다.
6. $\sim$ 이 대칭관계가 아니면 유향 그래프^digraph라 한다.
7. 유한 집합 $V$ 에 대해 대칭관계 $\sim \subset \left\{ (v_{1} , v_{2} ) \in V^2 \mid v_{1} \ne v_{2} \right\}$ 를 에지가지며 두 버텍스를 잇는 에지가 하나뿐인 그래프를 심플 그래프라고 한다.