그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭지점과 7개의 변을 갖는 그래프의 다이어그램.

그래프(graph, 문화어: 그라프)는 그래프 이론에서 다루는 수학 용어이다. 그래프는 꼭짓점(또는 정점)(vertex)과 변(邊, edge)으로 이루어져 있다. 흔히 그래프를 꼭짓점의 집합과 두 꼭짓점을 잇는 변의 집합의 순서쌍으로 정의한다. (예를 들어, 꼭지점의 집합 V와 변의 집합 E를 포함하는 그래프 G(V,E)로 표현한다.) 변에 방향을 허용하느냐 마느냐에 따라서 방향이 있는 그래프, 혹은 방향이 없는 그래프로 나뉜다. 그래프의 변이 방향을 가지고 있으면 그 그래프를 유향 그래프(有向-, directed graph, 혹은 digraph)라고 한다. 반대로 변이 방향을 가지고 있지 않는 경우는 무향 그래프(無向-, undirected graph)라고 한다.

그래프는 여러 자원/도시 간의 연결 상태를 추상화해서 나타낼 수 있기 때문에 여러 분야에서 응용이 되고 있다.

정의[편집]

그래프는 꼭지점의 집합 V와 변의 집합 E의 순서쌍 (V,E)로 정의한다. 변은 두 꼭지점을 잇는다. 예를 들어 두 꼭지점 v_1v_2를 잇는 변 e(v_1, v_2)로 표현할 수 있다.

그래프는 그 형태에 따라 여러가지 종류로 나뉜다. 크게는 무향 그래프(undirected graph)와 유향 그래프(directed graph)로 나뉜다. 변이 방향성을 띠지 않는 그래프를 무향그래프, 방향성을 띠는 그래프를 유향그래프라고 한다. 그래프 이론을 연구하는 사람들은 이렇게 다양한 형태의 그래프가 가지는 특성을 연구하고, 이를 컴퓨터 네트워크와 같은 다른 분야에 적용하기도 한다.

무향 그래프[편집]

무향 그래프(undirected graph)는 변이 방향을 가지지 않고 두 개의 꼭지점을 연결하고 있는 그래프이다.

  • 단순 그래프(simple graph)
꼭지점 집합 V와 변의 집합인 E로 이루어지는 단순 그래프 G = (V,E)는 두 개의 꼭지점 v_1v_2사이에 최대한 한 개의 변만을 허용하고 각 변은 서로 다른 두 꼭지점에 접하여야 하는 무향그래프이다.
(예) G = (V,E)가 단순그래프이고, e_1 = (v_1,v_2), \ e_2 = (v_1, v_2)일 때, e_1 \in E 라면, e_2 \not\in E이다.
  • 다중 그래프(multigraph)
다중 그래프는 단순 그래프와 비슷하지만, 두 개의 꼭지점 사이에 여러 개의 변이 있을 수 있다.
(예) e_1 = (v_1,v_2), \ e_2 = (v_1, v_2), \ e_1, e_2 \in E

유향 그래프[편집]

  • 유향 그래프(directed graph 또는 digraph)
유향 그래프는 변이 방향성을 지닌다. 이때, 이 변을 유향변이라 한다.
(예)v_1, v_2 \in V일 때, (v_1,v_2) \neq (v_2,v_1) 이다.
  • 유향다중 그래프(directed multigraph)
다중 그래프와 같이, 유향다중 그래프는 동일한 두 개의 꼭지점을 잇는 유향변이 여러 개 있을 수 있다.

그래프 사이의 관계[편집]

  • 부분 그래프(subgraph)
두 개의 그래프 G = (V,E) H = (W,F)가 있고, W \subseteq VF \subseteq E가 성립하면, HG의 부분 그래프이다.

꼭짓점의 차수[편집]

어떤 꼭짓점의 차수라는 것은 그 꼭짓점을 끝점으로 하는 변(또는 간선)이 몇 개인가를 의미한다. 만약 그래프가 유향 그래프(directed graph)인 경우에는 꼭짓점의 차수를 두 종류로 나누어서 들어오는 변의 수를 나타내는 차수와 나가는 변의 수를 나타내는 차수를 구분하여 표현할 수도 있다.

꼭짓점 차수의 특성[편집]

어떤 그래프에 있는 모든 꼭짓점 차수의 합은 이 그래프가 가진 변의 수의 두 배가 된다. 따라서, 꼭짓점 차수의 합은 짝수가 되면, 차수가 홀수인 꼭짓점의 수도 짝수가 된다는 성질을 가진다.

그래프의 속성들[편집]

그래프에서 두 개의 꼭지점이 같은 변을 공유할 때 이를 '근접(adjacent)하다'라고 정의한다. 비슷한 방식으로 두 개의 변이 동일한 꼭지점을 가지면 이도 '근접(adjacent)하다'라고 하고 공통 변은 두 개의 꼭지점을 'Join 한다'라고 한다. 이 변에서 변과 꼭지점을 incident 라 한다.

한 개의 꼭지점만으로 이루어진 그래프를 trivial graph 라 한다. 변이 없이 꼭지점만으로 이루어진 그래프를 edgeless graph 라 한다. 꼭지점과 변이 모두 없는 그래프는 null graph 또는 empty graph 라 하나, 수학자들은 이러한 경우를 허용하지 않는다.

그래프의 종류[편집]

용어에 대한 설명[편집]

그래프라는 용어를 사용할 때는 여러 가지 맥락에서 사용될 수 있다. 정확한 정의가 필요한 경우에는 다음의 용어들을 사용한다. 그렇지 않은 경우 대부분의 일반적인 경우에는 그래프라고 하면 "무향 단순 유한 그래프 (undirected simple finite graph)"를 의미한다.

중요한 그래프들[편집]

완전 그래프는 그래프에 속하는 모든 꼭지점이, 다른 꼭지점과 인접해 있는 그래프이다. 완전 그래프의 꼭지점들은 모두 같은 개수의 꼭지점과 연결되어 있기 때문에 완전 그래프는 정규 그래프이다.
n개의 꼭지점을 가진 완전 그래프는 \frac {n(n-1)} 2개의 변을 가지고 있다.
꼭지점의 집합이 V_1V_2의 합집합이고, 모든 V_1의 꼭지점이 V_2의 꼭지점 각각과 변으로 연결되어 있는 경우 완전 이분 그래프라 한다.
그래프 G = (V,E)에서, 꼭지점 집합 V를 두 개의 집합 V_1V_2로 나누되 모든 변은 V_1의 꼭지점과 V_2의 꼭지점과 동시에 접하도록 할 수 있는 경우 G를 이분 그래프라고 한다.
모든 꼭지점(vertex)이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭지점에 연결된 이웃이 k 개인 경우, k-정규 그래프라 불린다.
평면 상에 꼭지점과 변을 그리되 변과 변이 꼭지점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프를 평면 그래프라 한다.
모든 꼭지점들이 연결되어 있고 회로를 포함하지 않는 그래프이다.

같이 보기[편집]