그래프

Article on other languages:

다른 뜻에 대해서는 그래프 (동음이의) 문서를 참조하십시오.
6개의 꼭지점과 7개의 변을 갖는 그래프의 다이어그램.

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

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

목차

정의

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

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

무향 그래프

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

  • 단순 그래프(simple graph)
꼭지점 집합 V와 변의 집합인 E로 이루어지는 단순 그래프 G = (V,E)는 두 개의 꼭지점 v1과 v2사이에 최대한 한 개의 변만을 허용하고 각 변은 서로 다른 두 꼭지점에 접하여야 하는 무향그래프이다.
(예) 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)
유향 그래프는 변이 방향성을 지닌다.
(예)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 V 와 F \subseteq E가 성립하면, H는 G의 부분 그래프이다.

그래프 속성들

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

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


몇몇 중요한 그래프

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

같이 보기

원본 주소 ‘http://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84’

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.