그래프(Graph)란?

그래프란? 쉽게 한 문장으로 설명한다면, 현실 세계의 관계를 시각적으로 나타낼 수 있는 구조. 라고 할 수 있다.

우리는 일상에서 다음과 같은 곳에서 그래프를 사용한다.

그래프를 사용하면 객체간의 관계를 쉽게 나타낼 수 있다는 장점으로 많이 사용한다.

이를 전문적인 용어로 말 한다면 정점과 간선의 집합으로 구성되며 수학적으로는 G = (V, E)의 관계로 나타난다. 처음 보는 사람들은 이해가 안 갈 수도 있는데, 한 번 따라가 보자.

그래프의 종류

그래프의 종류는 다음과 같은 세 가지로 나뉜다.

무항향 그래프는 간선에 방향이 표시되어있지 않은 그래프를 무방향 그래프라고 한다.

여기서 하나의 간선은 양방향으로 갈수 있는 길을 의미하고 (A, B)나 (B, A)은 같은 간선이 된다.

간선에 방향이 존재하는 그래프를 방향 그래프라고 한다.

보통 화살표로 표시되는데 차도의 일방통행이라고 생각하면 쉽다.

<A, B>를 방향이 있는 그래프에서 표시하는데 <A, B>는 정점 A에서 B로만 갈 수 있는 간선을 나타낸다. 그 말은 당연히 <A, B>와 <B, A>는 다른 그래프를 뜻한다.

간선의 비용이나 가중치가 할당된 그래프를 가중치 그래프라고 한다.