그래프(Graph) & 트리(Tree)

그래프(Graph)

 

그래프란 정점과 간선으로 이루어진 집합을 말한다.

그림 1

 

이런 이미지가 있다고 할 때 숫자가 쓰여있는 원을 정점

정점 사이를 잇는 선을 간선 이라고 한다.

 

이때 간선은 두 정점 사이 여러 개 있을 수 있으며, 방향이 존재하거나 가중치가 존재하는 등 여러 형태가 있으며,

이를 이용한 다양한 그래프가 존재한다.

 

트리(Tree)

 

트리란 그래프의 종류 중 하나로 나무처럼 생겼다고 해서 붙여진 그래프의 하위분류이다.

 

그림 2

 

트리는 그래프와 비슷하게 생겼지만 방향을 제외했을 때, 사이클이 존재하면 안 된다.

그림 1은 그래프는 될 수 있지만 2-3-4-5의 사이클이 존재하기 때문에 트리일 수 없다.

그림 2는 사이클이 존재하지 않기 때문에 그래프와 트리 모두 해당된다.

 

또 그래프는 다른 정점들과 떨어진 정점들의 집합도 그래프라고 보지만,

트리는 방향을 제외했을 때, 임의의 정점에서 다른 모든 정점으로 갈 수 있을 때를 트리라고 한다.

 

정리해 보면,

1. 사이클이 존재하면 안 된다.

2. 방향이 없을 때, 임의의 정점에서 다른 모든 정점으로 이동할 수 있다.

이 두 가지의 조건을 만족할 때, 우리를 하나의 트리라고 할 수 있다.

 

 

만약 10에서 14로 가는 간선이 없다면, 그림 2는 하나의 트리가 아니다.

물론 문제에선 여러 개의 트리를 사용하는 경우가 있어,

이를 좀 더 생각해 보면, 2개의 그래프 또는 트리라고 할 수 있다.

 

이런 트리와 그래프는 여러 알고리즘에서 쓰이며, 실생활에서도 많이 쓰인다.

예를 들면, 내비게이션에서 A 지점에서 B로 갈려고 할 때 길을 안내해 준다. 이때 그래프가 사용된다.

 

앞으로 트리와 그래프를 이용한 알고리즘들을 많이 소개할 것이다.