그래프

위키백과 ― 우리 모두의 백과사전.

다른 뜻에 대해서는 그래프 (동음이의) 문서를 참고하십시오.

6개의 꼭지점과 7개의 변을 갖는 그래프의 다이어그램.

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

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

[편집] 정의

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

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

[편집] 무향 그래프

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

단순 그래프(simple graph)

꼭지점 집합

V

와 변의 집합인 E로 이루어지는 단순 그래프 $G = (V,E) \;$ 는 두 개의 꼭지점 $v_1 \;$ 과 $v_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)

유향 그래프는 변이 방향성을 지닌다.

(예) $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 라 하나, 수학자들은 이러한 경우를 허용하지 않는다.