그래프(이산수학)
[image]
1. 개요
그래프는 정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성이 된다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirected graph)라고 말한다. 그리고 변의 경우에는 특정한 수치를 가질 수 있는데 이를 가중치(Weighted value)라고 말한다.
예를 들어 도시를 정점으로 생각하고 도시 사이를 잇는 도로를 변으로 생각하면 그래프는 곧 하나의 간략화된 지도가 된다. 위의 그림에서 1~6번 원이 도시고 연결선이 도로인 셈. 여기에 각 도로마다 도로의 길이 또는 이용 요금을 써 넣으면 이것이 바로 그 도로의 가중치이다.
위에서 알 수 있듯이 그래프는 도시와 도로로도 비유될 수 있기 때문에 두 지점 간의 최단 경로(또는 가장 저렴한 경로)를 구하는 데 널리 이용된다. 그래프는 도시-도로뿐만 아니라 컴퓨터 통신망, SNS에서의 친구관계 등등 여러 상황을 모델링 할 수 있어 많은 분야에서 널리 사용된다. 예를 들어 어떤 웹 페이지를 정점으로 하고 페이지에 달린 링크들을 다른 페이지로 가는 변이라고 보면, 나무위키 역시 하나의 거대한 그래프라고 볼 수 있다.
위의 그림에서는 2,3,4,5번 도시(정점)들이 서로 연결되어 순환할 수 있다. 다시 말해서 2번 도시에서 출발하여 3,4,5번 도시를 거쳐 다시 2번에 도착할 수 있다는 것. 이와는 반대로, 이렇게 순환하지 않는 그래프를 특히 트리(그래프)라고도 부른다.
순수수학에서는 수학자 오일러가 한붓그리기 문제, 즉 쾨니히스베르크 다리 건너기 문제를 푼 것을 그래프 이론의 시작으로 보고 있다. 이 외에도 그래프 이론에서 대중에게 비교적 친숙한 문제로는 4색 정리나 해밀턴 경로[1] 등이 있을 것이다.
과거 2007 개정 교육과정까지 고등학교 수학에 등장했던 '행렬과 그래프'라는 단원에서의 그래프는 해석학적인 그래프가 아니라 바로 이 그래프를 뜻한다.
2. 용어와 정의
그래프는 일반적으로 위 그림과 같이 점과 선분을 이용한 그림으로써 표현되는 경우가 많다. 그러나 그래프 이론 또한 수학의 한 분야인 이상, 이를 이용하여 정리를 세우거나, 각종 문제를 풀기 위해서는 우선 그래프와 그에 관련된 개념을 수학적으로 엄밀하게 정리할 필요가 있다. 그래프와 관련된 용어는 집합과 함수 등을 이용하여 정의될 수 있다.
예를 들어, 위 그림의 그래프를 $$G = (V, E)$$라 했을 때 꼭짓점의 집합 $$V$$와 변의 집합 $$E$$를 엄밀하게 정의하면 다음과 같다.
$$\displaystyle \begin{aligned} &V = \{1, 2, 3, 4, 5, 6\} \\ &E = \left\{ \{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\} \right\} \end{aligned} $$
[1] 모든 정점들을 한 번씩만 지나는 경로
2.1. 그래프의 정의와 변형
그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 전산학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다.
2.1.1. 그래프
'''그래프'''(graph) $$G$$는 꼭짓점의 집합 $$V$$[2]와 변의 집합 $$E$$의 순서쌍으로 정의된다. 즉,
당연하게도 $$V$$의 원소는 '''꼭짓점'''(vertex), $$E$$의 원소는 '''변'''(모서리, edge)라 부른다. 흔히 그림에서 꼭지점은 점이나 원으로 표현되고, 변은 두 끝점을 잇는 선분으로 표현된다.
변의 집합 $$E$$는 모든 $$e \in E$$가 $$v_1, v_2 \in V$$에 대해
$$\displaystyle e = \{ v_1, v_2 \}$$
2.1.2. 유향그래프
그래프의 정의 중 $$e \in E$$에 대한 정의를 다음과 같이 바꾸어 준 것을 '''유향그래프'''(directed graph, digraph)라고 한다.
$$\displaystyle e \equiv (v_{1}, v_{2}) $$
한편, 유향그래프가 아닌 그래프를 '''무향그래프'''(비방향성 그래프, undirected graph)라 한다.
유향그래프는 무향그래프와 달리 두 정점 사이의 단방향적인 관계를 표현할 수 있다.
2.1.3. 다중그래프
'''다중그래프'''(multigraph)는 두 꼭짓점을 연결하는 변이 여러 개인 그래프이다. 엄밀하게는, 그래프의 정의를 다음과 같이 변형한 것을 다중그래프라고 한다.
$$\displaystyle G \equiv (V, E, \partial) $$
이전의 정의와는 달리, $$E$$의 원소, 즉 변은 '''끝점을 이용하여 정의되지 않는다.''' 그 대신 어떤 변이 어떤 두 끝점과 연결되는지를 함수 $$\partial$$로 정의하는 것이다. 예를 들어 $$\partial e_1 = \{u, v\}$$라면 변 $$e_1$$의 끝점은 $$u$$와 $$v$$라는 뜻이다. $$\partial e = \{u, v\}$$가 되는 변 $$e$$는 $$e_1$$ 이외에도 여러 개가 있을 수 있는데, 이 경우 두 꼭짓점은 여러 변과 연결되어 있다고 할 수 있는 것이다.
다중그래프가 아닌 그래프를 '''단순 그래프'''(simple graph)라 한다.
다중그래프는 단순그래프와 달리 두 정점 사이의 여러 관계를 표현할 수 있다.
2.1.3.1. 유향 다중그래프
다중 그래프에도 변의 방향을 적용하는 방법을 생각할 수 있다. 그러나 다중 그래프에서는 변의 두 끝점을 $$E$$의 정의가 아닌 새로운 함수 $$\partial$$를 이용해 결정했으므로, '''유향 다중그래프'''(directed multigraph)는 다음과 같이 $$\partial$$의 공역을 고쳐 새롭게 정의해야 한다.
$$\displaystyle \partial : E \to V^2$$
2.1.4. 가중 그래프
'''가중 그래프'''(weighted graph)는 각각의 변에 '''가중치'''(weight)라 불리는 값을 대응한 그래프이다. 엄밀하게는 가중치 함수 $$W : E \to \mathbb{R}$$를 추가한 그래프로 정의할 수 있다.
가중치는 그래프 모델이 쓰이는 상황에 따라 다르게 정의되어 다양하게 활용될 수 있다. 예를 들어 비행기의 항로를 그래프로 모델링한다면, 운항 거리, 시간, 항공비 등을 가중치로 고려할 수 있는데, 최단 경로 문제의 풀이법을 이용하면 '목적지까지 가장 빨리, 비용이 적게 도착할 수 있는 항공편은?' 같은 질문에 답할 수 있게 된다.
2.2. 특수한 그래프
2.2.1. 완전 그래프
Complete graph
모든 서로 다른 꼭짓점끼리 연결되는 그래프를 말한다. 이때 꼭짓점이 $$n$$개인 그래프를 n-완전 그래프(n-complete graph)라 하며, $$K_n$$로 쓴다.
꼭짓점의 개수가 $$n$$개일 때, 변의 개수는 $$n(n+1) \over 2$$개이며, 모든 꼭짓점의 차수는 $$n-1$$라는 성질이 있다.
완전 그래프가 아닌 그래프, 즉, 최소 한 쌍의 서로 연결되지 않은 꼭짓점 쌍이 존재하는 그래프를 '''불완전 그래프'''(incomplete graph)라 한다.
2.2.2. 사이클
$$i$$번째 꼭짓점을 $$v_i$$라고 할 때, '''사이클'''(cycle) $$C_n$$은 꼭짓점의 개수가 $$n$$개이며,
$$\displaystyle E = \left\{ v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, \cdots, v_{n-1}v_{n}, v_{n}v_{1} \right\} $$
2.2.3. 휠
$$i$$번째 꼭짓점을 $$v_i$$라고 할 때, '''휠'''(wheel) $$W_n$$은 꼭짓점의 개수가 $$n+1$$개이며,
$$\displaystyle E = \left\{ v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, \cdots, v_{n-1}v_{n}, v_{n}v_{1}, v_{1}v_{n+1}, v_{2}v_{n+1}, v_{3}v_{n+1}, \cdots, v_{n-1}v_{n+1}, v_{n}v_{n+1} \right\} $$
사이클 $$C_n$$에 새로운 꼭짓점 $$v_{n+1}$$을 추가하고, $$C_n$$에 있던 꼭짓점들과 $$v_{n+1}$$을 서로 연결함으로써 만들 수 있다.
2.2.4. 기타 그래프의 분류
- 무한 그래프(infinite graph): $$V$$가 무한집합인 그래프. 즉, 꼭짓점의 개수가 무한한 그래프를 말한다. 무한 그래프가 아닌 그래프는 유한 그래프(finite graph)다.
2.3. 정점과 관련된 용어
2.3.1. 이웃
'''꼭짓점''' $$v$$에 대해서, $$v$$의 '''이웃'''(neighborhood) 또는 '''인접'''(adjacent)은 $$v$$와 이웃한(neighbor) 꼭짓점들의 집합이며, 기호로는 $$N(v)$$와 같이 쓴다. 예를 들어 단순 무향 그래프인 경우에는 다음과 같다.
$$\displaystyle N(v) = \left\{u \in V | \left\{u, v \right\} \in E \right\}$$
$$\displaystyle N(A) \equiv \bigcup_{v \in A}N(v)$$
2.3.2. 차수
'''무향''' 그래프의 꼭짓점 $$v$$의 '''차수'''(degree)는 기호로 $$\operatorname{deg}(v)$$ 또는 $$d(v)$$라 쓰며, 다음과 같이 정의된다.
$$\displaystyle \operatorname{deg}(v) \equiv \left| N(v) \right| + 2\left|\left\{ \{v\} \in E \right\}\right| $$
- $$\operatorname{deg}(v)$$를 $$v$$와 연결된 고리(loop)가 아닌 모서리의 개수로 정한다.
- $$v$$와 연결된 고리의 개수당 2를 더한다.
2.3.3. 입력차수와 출력차수
'''유향''' 그래프의 꼭짓점 $$v$$의 '''입력차수'''(in-degree) $$\operatorname{deg}^{-}(v)$$와 '''출력차수'''(out-degree) $$\operatorname{deg}^{+}(v)$$는 다음과 같이 정의된다.
$$\displaystyle \begin{aligned} \operatorname{deg}^{-}(v) \equiv& \left|\left\{ u \in V | (u, v) \in E \right\}\right| \\ \operatorname{deg}^{+}(v) \equiv& \left|\left\{ u \in V | (v, u) \in E \right\}\right| \end{aligned} $$
[각주]