그래프

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

그래프 이론에서, 그래프(영어: graph, 문화어: 그라프)는 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다. 변에 방향을 허용하느냐 마느냐에 따라서 방향이 있는 그래프, 혹은 방향이 없는 그래프로 나뉜다. 그래프의 변이 방향을 가지고 있으면 그 그래프를 유향 그래프(有向-, directed graph, 혹은 digraph)라고 한다. 반대로 변이 방향을 가지고 있지 않는 경우는 무향 그래프(無向-, undirected graph)라고 한다. 그래프의 개념은 정보과학 등에서 다양한 데이터를 나타내기 위해 응용된다.

정의[편집]

무향 그래프 \Gamma=(V,E)는 집합 V와, V의 1 또는 2원소 부분집합들로 구성된 집합 E의 순서쌍이다. 즉, 모든 e\in E에 대하여, 다음이 성립한다.

e\subset V
|e|\in\{1,2\}

여기서 V를 그래프의 꼭짓점 집합(영어: set of vertices), E를 그래프의 변 집합(영어: set of edges</math>이라 하고, 보통 각각 V(\Gamma), E(\Gamma)로 쓴다. 만약 e=\{u,v\}라면, 이를 꼭짓점 u와 꼭지점 v 사이의 변이라고 한다. 만약 e=\{v\}라면, 이를 꼭짓점 v에서의 고리(영어: loop 루프[*])라고 한다.

유향 그래프\Gamma=(V,E)는 집합 V와, V의 순서쌍들로 구성된 집합 E\subset V\times V의 순서쌍이다. 이 경우, e=(u,v)라면 eu에서 v로 가는 변이라고 하며, 꼭짓점 v는 변 e머리(영어: head 헤드[*], 꼭짓점 u는 변 e꼬리(영어: tail 테일[*])라고 한다.

다른 수식어가 없는 경우, "그래프"는 보통 무향 그래프를 의미한다.

[편집]

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

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

[편집]

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

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

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

그래프의 속성들[편집]

(adjacent)하다라고 하고 공통 변은 두 개의 꼭짓점을 잇는다(영어: join 조인[*])고 한다. 이 변에서 변과 꼭짓점이 결합(영어: incident)한다고 한다.

그래프의 종류[편집]

  • 공그래프(영어: empty graph)는 꼭짓점과 변이 둘 다 없는 그래프이다. 즉, (V,E)=(\varnothing,\varnothing)이다.
  • 자명한 그래프(영어: trivial graph)는 한 개의 꼭짓점을 가지고, 변이 없는 그래프이다. 즉, E(\Gamma)=\varnothing이다.
  • 무변 그래프(영어: edgeless graph)는 변이 없는 그래프이다. 즉, E(\Gamma)=\varnothing이다.
  • 완전 그래프는 그래프에 속하는 모든 꼭짓점이, 다른 꼭짓점과 인접해 있는 그래프이다.
    • 완전 그래프의 꼭짓점들은 모두 같은 개수의 꼭짓점과 연결되어 있기 때문에 완전 그래프는 정규 그래프이다.
    • 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를 이분 그래프라고 한다.
  • 정규 그래프는 모든 꼭짓점이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭짓점에 연결된 이웃이 k 개인 경우, k-정규 그래프라 불린다.
  • 평면 그래프는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다.
  • 나무는 모든 꼭짓점들이 연결되어 있고 회로를 포함하지 않는 그래프이다.
  • 회로를 포함하지 않는 그래프이다.

같이 보기[편집]