[include(틀:이산수학·수리논리학)] [[파일:external/upload.wikimedia.org/333px-6n-graf.svg.png]] [목차] == 개요 == 그래프는 정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성이 된다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirected graph)라고 말한다. 그리고 변의 경우에는 특정한 수치를 가질 수 있는데 이를 가중치(Weighted value)라고 말한다. 예를 들어 도시를 정점으로 생각하고 도시 사이를 잇는 도로를 변으로 생각하면 그래프는 곧 하나의 간략화된 지도가 된다. 위의 그림에서 1~6번 원이 도시고 연결선이 도로인 셈. 여기에 각 도로마다 도로의 길이 또는 이용 요금을 써 넣으면 이것이 바로 그 도로의 가중치이다. 위에서 알 수 있듯이 그래프는 도시와 도로로도 비유될 수 있기 때문에 두 지점 간의 최단 경로(또는 가장 저렴한 경로)를 구하는 데 널리 이용된다. 그래프는 도시-도로뿐만 아니라 컴퓨터 통신망, [[SNS]]에서의 친구관계 등등 여러 상황을 모델링 할 수 있어 많은 분야에서 널리 사용된다. 예를 들어 어떤 웹 페이지를 정점으로 하고 페이지에 달린 링크들을 다른 페이지로 가는 변이라고 보면, 나무위키 역시 하나의 거대한 그래프라고 볼 수 있다. 위의 그림에서는 2,3,4,5번 도시(정점)들이 서로 연결되어 순환할 수 있다. 다시 말해서 2번 도시에서 출발하여 3,4,5번 도시를 거쳐 다시 2번에 도착할 수 있다는 것. 이와는 반대로, 이렇게 순환하지 않는 그래프를 특히 [[트리(그래프)]]라고도 부른다. 순수수학에서는 수학자 [[오일러]]가 한붓그리기 문제, 즉 [[쾨니히스베르크 다리 건너기 문제]]를 푼 것을 그래프 이론의 시작으로 보고 있다. 이 외에도 그래프 이론에서 대중에게 비교적 친숙한 문제로는 [[4색 정리]]나 해밀턴 경로[* 모든 정점들을 한 번씩만 지나는 경로] 등이 있을 것이다. 과거 [[2007 개정 교육과정/고등학교/수학과|2007 개정 교육과정]]까지 고등학교 수학에 등장했던 '행렬과 그래프'라는 단원에서의 그래프는 해석학적인 그래프가 아니라 바로 이 그래프를 뜻한다. == 용어와 정의 == 그래프는 일반적으로 위 그림과 같이 점과 선분을 이용한 그림으로써 표현되는 경우가 많다. 그러나 그래프 이론 또한 수학의 한 분야인 이상, 이를 이용하여 정리를 세우거나, 각종 문제를 풀기 위해서는 우선 그래프와 그에 관련된 개념을 수학적으로 엄밀하게 정리할 필요가 있다. 그래프와 관련된 용어는 집합과 함수 등을 이용하여 정의될 수 있다. 예를 들어, 위 그림의 그래프를 [math(G = (V, E))]라 했을 때 꼭짓점의 집합 [math(V)]와 변의 집합 [math(E)]를 엄밀하게 정의하면 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\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} )]}}} 그래프 이론이 비교적 최근에 생긴 이론인 만큼 시간대나 활용하는 분야에 따라 같은 정의라도 용어가 다르거나, 심지어 정의 자체가 다른 경우도 있다. 그러므로 [[위키러]]는 상황에 따라 용어를 유동적으로 해석할 수 있어야 하며, 정의를 분명하게 명시해야만 한다. 예를 들어 '꼭짓점(vertex)'은 [[컴퓨터공학]]을 비롯한 공학계열에서는 '[[노드]](node)'라는 이름으로 불리기도 한다. 사정이 이렇다보니 이를 번역한 교재에 따라 한국어 번역이 중구난방이다. === 그래프의 정의와 변형 === 그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 전산학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다. ==== 그래프 ==== '''그래프'''(graph) [math(G)]는 꼭짓점의 집합 [math(V)][* 보통 따로 명시되지 않는 이상 [math(V \neq \varnothing)]이다.]와 변의 집합 [math(E)]의 [[순서쌍]]으로 정의된다. 즉, {{{#!wiki style="text-align: center" [br][math(\displaystyle G \equiv (V, E) )]}}} 당연하게도 [math(V)]의 원소는 '''꼭짓점'''(vertex), [math(E)]의 원소는 '''변'''(모서리, edge)라 부른다. 흔히 그림에서 꼭지점은 점이나 원으로 표현되고, 변은 두 끝점을 잇는 선분으로 표현된다. 변의 집합 [math(E)]는 모든 [math(e \in E)]가 [math(v_1, v_2 \in V)]에 대해 {{{#!wiki style="text-align: center" [br][math(\displaystyle e = \{ v_1, v_2 \})]}}} 가 되도록 정의한다. 이 때 [math(v_1, v_2)]를 [math(e)]의 '''끝점'''(endpoint)이라 하고, [math(v_1)]과 [math(v_2)]는 서로 '''인접한다'''(adjacent) 또는 '''이웃한다'''(neighbor)고 한다. '[math(e)]는 [math(v_1, v_2)]와 '''붙어있다'''(incident)' 또는 '[math(v_1, v_2)]를 '''연결한다'''(connect)'고 한다. 두 꼭짓점 [math(v_1)], [math(v_2)]를 연결하는 변을 간단히 [math(v_{1}v_{2})]와 같이 표기하기도 한다. ==== 유향그래프 ==== 그래프의 정의 중 [math(e \in E)]에 대한 정의를 다음과 같이 바꾸어 준 것을 '''유향그래프'''(directed graph, digraph)라고 한다. {{{#!wiki style="text-align: center" [br][math(\displaystyle e \equiv (v_{1}, v_{2}) )]}}} 보다시피, 순서를 나타내기 위해 [[집합]]이 아닌 [[순서쌍]]을 이용하였다. 여기서 [math(e)]는 '''유향변'''(방향모서리, directed edge 또는 arc)이라고 한다. 이때, [math(v_1)]은 [math(e)]의 '''시점''', [math(v_2)]은 [math(e)]의 '''종점'''이라 하며, '[math(e)]는 [math(v_1)]에서 시작하여 [math(v_2)]에서 끝난다', 또는 '[math(v_1)]에서 [math(v_2)]로 간다'와 같이 표현한다. 흔히 그림에서 유향변은 시점에서 종점으로 향하는 화살표로 표현된다. 한편, 유향그래프가 아닌 그래프를 '''무향그래프'''(비방향성 그래프, undirected graph)라 한다. 유향그래프는 무향그래프와 달리 두 정점 사이의 단방향적인 관계를 표현할 수 있다. ==== 다중그래프 ==== '''다중그래프'''(multigraph)는 두 꼭짓점을 연결하는 변이 여러 개인 그래프이다. 엄밀하게는, 그래프의 정의를 다음과 같이 변형한 것을 다중그래프라고 한다. {{{#!wiki style="text-align: center" [br][math(\displaystyle G \equiv (V, E, \partial) )]}}} 여기서 [math(\partial : E \to S^2(V))]는 [[함수]]이고, [[공역]] [math(S^2(V) = \left\{ \left\{ u, v \right\}|u, v \in V \right\})]이다. 즉, [math(S^2(A))]는 [math(A)]의 부분집합들 중 원소가 2개인 것만 원소로 하는 [[집합족]]이다. 이전의 정의와는 달리, [math(E)]의 원소, 즉 변은 '''끝점을 이용하여 정의되지 않는다.''' 그 대신 어떤 변이 어떤 두 끝점과 연결되는지를 함수 [math(\partial)]로 정의하는 것이다. 예를 들어 [math(\partial e_1 = \{u, v\})]라면 변 [math(e_1)]의 끝점은 [math(u)]와 [math(v)]라는 뜻이다. [math(\partial e = \{u, v\})]가 되는 변 [math(e)]는 [math(e_1)] 이외에도 여러 개가 있을 수 있는데, 이 경우 두 꼭짓점은 여러 변과 연결되어 있다고 할 수 있는 것이다. 다중그래프가 아닌 그래프를 '''단순 그래프'''(simple graph)라 한다. 다중그래프는 단순그래프와 달리 두 정점 사이의 여러 관계를 표현할 수 있다. ===== 유향 다중그래프 ===== 다중 그래프에도 변의 방향을 적용하는 방법을 생각할 수 있다. 그러나 다중 그래프에서는 변의 두 끝점을 [math(E)]의 정의가 아닌 새로운 함수 [math(\partial)]를 이용해 결정했으므로, '''유향 다중그래프'''(directed multigraph)는 다음과 같이 [math(\partial)]의 [[공역]]을 고쳐 새롭게 정의해야 한다. {{{#!wiki style="text-align: center" [br][math(\displaystyle \partial : E \to V^2)]}}} 여기서 [math(V^2 = V \times V = \left\{ \left( u, v \right)|u, v \in V \right\})]이다. 즉, 유향 그래프와 마찬가지로 두 꼭짓점들의 집합을 순서쌍으로 바꾼 것이다. ==== 가중 그래프 ==== '''가중 그래프'''(weighted graph)는 각각의 변에 '''가중치'''(weight)라 불리는 값을 대응한 그래프이다. 엄밀하게는 가중치 [[함수]] [math(W : E \to \mathbb{R})]를 추가한 그래프로 정의할 수 있다. 가중치는 그래프 모델이 쓰이는 상황에 따라 다르게 정의되어 다양하게 활용될 수 있다. 예를 들어 비행기의 항로를 그래프로 모델링한다면, 운항 거리, 시간, 항공비 등을 가중치로 고려할 수 있는데, 최단 경로 문제의 풀이법을 이용하면 '목적지까지 가장 빨리, 비용이 적게 도착할 수 있는 항공편은?' 같은 질문에 답할 수 있게 된다. === 특수한 그래프 === ==== 완전 그래프 ==== Complete graph 모든 서로 다른 꼭짓점끼리 연결되는 그래프를 말한다. 이때 꼭짓점이 [math(n)]개인 그래프를 n-완전 그래프(n-complete graph)라 하며, [math(K_n)]로 쓴다. 꼭짓점의 개수가 [math(n)]개일 때, 변의 개수는 [math(n(n+1) \over 2)]개이며, 모든 꼭짓점의 차수는 [math(n-1)]라는 성질이 있다. 완전 그래프가 아닌 그래프, 즉, 최소 한 쌍의 서로 연결되지 않은 꼭짓점 쌍이 존재하는 그래프를 '''불완전 그래프'''(incomplete graph)라 한다. ==== 사이클 ==== [math(i)]번째 꼭짓점을 [math(v_i)]라고 할 때, '''사이클'''(cycle) [math(C_n)]은 꼭짓점의 개수가 [math(n)]개이며, {{{#!wiki style="text-align: center" [br][math(\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\} )]}}} 인 그래프이다. ==== 휠 ==== [math(i)]번째 꼭짓점을 [math(v_i)]라고 할 때, '''휠'''(wheel) [math(W_n)]은 꼭짓점의 개수가 [math(n+1)]개이며, {{{#!wiki style="text-align: center" [br][math(\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\} )]}}} 인 그래프이다. 사이클 [math(C_n)]에 새로운 꼭짓점 [math(v_{n+1})]을 추가하고, [math(C_n)]에 있던 꼭짓점들과 [math(v_{n+1})]을 서로 연결함으로써 만들 수 있다. ==== 기타 그래프의 분류 ==== * '''무한 그래프'''(infinite graph): [math(V)]가 무한집합인 그래프. 즉, 꼭짓점의 개수가 무한한 그래프를 말한다. 무한 그래프가 아닌 그래프는 유한 그래프(finite graph)다. === 정점과 관련된 용어 === ==== 이웃 ==== '''꼭짓점''' [math(v)]에 대해서, [math(v)]의 '''이웃'''(neighborhood) 또는 '''인접'''(adjacent)은 [math(v)]와 이웃한(neighbor) 꼭짓점들의 집합이며, 기호로는 [math(N(v))]와 같이 쓴다. 예를 들어 단순 무향 그래프인 경우에는 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\displaystyle N(v) = \left\{u \in V | \left\{u, v \right\} \in E \right\})]}}} '''꼭짓점의 집합''' [math(A)]에 대해서, [math(A)]의 이웃은 모든 [math(v \in A)]의 이웃의 합집합이다. 즉 다음과 같다. {{{#!wiki style="text-align: center" [br][math(\displaystyle N(A) \equiv \bigcup_{v \in A}N(v))]}}} ==== 차수 ==== '''무향''' 그래프의 꼭짓점 [math(v)]의 '''차수'''(degree)는 기호로 [math(\operatorname{deg}(v))] 또는 [math(d(v))]라 쓰며, 다음과 같이 정의된다. {{{#!wiki style="text-align: center" [br][math(\displaystyle \operatorname{deg}(v) \equiv \left| N(v) \right| + 2\left|\left\{ \{v\} \in E \right\}\right| )]}}} 즉, 모든 [math(v)]와 연결된 모서리에 대해 다음의 과정을 통해 정의될 수 있다. * [math(\operatorname{deg}(v))]를 [math(v)]와 연결된 고리(loop)가 아닌 모서리의 개수로 정한다. * [math(v)]와 연결된 고리의 개수당 '''2를 더한다.''' 차수는 꼭짓점에 연결된 모서리의 수를 나타내는데, 고리에 대해 2를 더하는 것은 고리를 포함하는 그래프에서 일반적인 성질을 유지하기 위한 장치이다. ==== 입력차수와 출력차수 ==== '''유향''' 그래프의 꼭짓점 [math(v)]의 '''입력차수'''(in-degree) [math(\operatorname{deg}^{-}(v))]와 '''출력차수'''(out-degree) [math(\operatorname{deg}^{+}(v))]는 다음과 같이 정의된다. {{{#!wiki style="text-align: center" [br][math(\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} )]}}} 즉, 입력차수와 출력차수는 [math(v)]를 종점과 시점으로 갖는 모서리의 수이다. 단, 고리(loop)는 입, 출력차수 모두에 1씩 영향을 미친다. [각주] [include(틀:문서 가져옴, title=그래프, version=69, paragraph=3)] [[분류:자료구조]][[분류:그래프]]