그래프

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

이 문서는 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

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

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

목차 1 정의 1.1 무향 그래프 1.2 유향 그래프 2 그래프 사이의 관계 3 몇몇 중요한 그래프 4 같이 보기

[편집] 정의

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

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

[편집] 무향 그래프

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

• 단순 그래프(simple graph)

꼭지점 집합 V와 변의 집합인 E로 이루어지는 단순 그래프 는 두 개의 꼭지점 과 사이에 최대한 한 개의 변만을 허용하고 각 변은 서로 다른 두 꼭지점에 접하여야 하는 무향그래프이다.

(예) 가 단순그래프이고, , 일 때, 라면, 이다.

• 다중 그래프(multigraph)

다중 그래프는 단순 그래프와 비슷하지만, 두 개의 꼭지점 사이에 여러 개의 변이 있을 수 있다.

(예) , ,

[편집] 유향 그래프

• 유향 그래프(directed graph)

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

(예)일 때, 이다.

• 유향다중 그래프(directed multigraph)

다중 그래프와 같이, 유향다중 그래프는 동일한 두 개의 꼭지점을 잇는 변이 여러 개 있을 수 있다.

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

• 부분 그래프(subgraph)

두 개의 그래프 와 가 있고, 와 가 성립하면, 는 의 부분 그래프이다.

[편집] 몇몇 중요한 그래프

• 완전 그래프(complete graph)

완전 그래프는 그래프에 속하는 모든 꼭지점이, 다른 꼭지점과 인접해있는 그래프이다. n개의 꼭지점을 가진 완전 그래프는 n(n-1)/2개의 변을 가지고 있다.

• 완전 이분 그래프(complete bipartite graph)

꼭지점의 집합이 V₁과 V₂의 합집합이고, 모든 V₁의 꼭지점이 V₂의 꼭지점 각각과 변으로 연결되어 있는 경우 완전 이분 그래프라 한다.

• 이분 그래프(bipartite graph)

그래프 G = (V,E)에서, 꼭지점 집합V를 두 개의 집합 와 로 나누되 모든 변은 V₁의 꼭지점과 V₂의 꼭지점과 동시에 접하도록 할 수 있는 경우 G를 이분 그래프라고 한다.

• 정규 그래프(regular graph)

모든 꼭지점(vertex)이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다.

• 평면 그래프(planar graph)

평면 상에 꼭지점과 변을 그리되 변과 변이 꼭지점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프를 평면 그래프라 한다.

[편집] 같이 보기

• 그래프 이론
• 그래프 이론 용어사전