그래프 (Graph)

그래프 (Graph) ?

도입

• 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다.
  • 우리 주변에서 찾을 수 있는 예를 들면, 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 있을 것이다.

 

그래프의 정의

• 그래프 $G(V, E)$ 는 아래 요소들로 구성된 자료 구조이다.
  • 어떤 자료나 개념을 표현하는 정점 (Vertex) 들의 집합 $V$.
  • 정점들을 연결하는 간선 (Edge) 들의 집합 $E$.
• 아래 그림은 1 ~ 5까지의 번호가 주어진 정점들과 이들을 연결하는 간선으로 구성된 그래프들의 예시다.

• 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다.
  • 따라서 다른 모양이지만 위 그림은 모두 같은 그래프를 표현한 것이다.

 

그래프의 종류

• 그래프는 표현하고자 하는 대상에 따라 여러 가지 변형된 형태를 가질 수 있다.
  • 이들은 정점이나 간선에 추가적인 속성을 부여할 수도 있고, 존재할 수 있는 간선이나 정점의 형태에 제약을 둘 수도 있다.

방향 그래프 (Directed Graph) / 유향 그래프 ↔ 무향 그래프 (Undirected Graph)

• 방향 그래프에서는 각 간선이 방향이라는 새로운 속성을 갖는다.
  • 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다.

• 이와는 반대로 간선에 방향이 없는 그래프를 무향 그래프라고 한다.

가중치 그래프 (Weighted Graph)

• 가중치 그래프는 각 간선에 가중치 (Weight) 라는 실수 속성을 부여한다.
  • 이 속성은 두 도시 사이의 거리, 두 물건 사이의 교환 비율 등의 다양한 정보를 표현하는 데 사용한다.

그래프의 형태로 그래프를 분류

다중 그래프 (Multigraph)

• 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프를 말한다.

이분 그래프 (Bipartite Graph)

• 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프를 말한다.
• 아래 그림의 정점들을 검은색 정점과 흰색 정점으로 나눠 보자.
  • 색이 같은 정점들 간에는 간선이 없는 것을 볼 수 있다.

DAG (사이클이 없는 방향 그래프, Directed Acyclic Graph)

• 한 그래프가 두 가지 이상의 속성을 함께 가지는 경우이다.
• 한 점에서 출발해 자기 자신으로 돌아오는 경로 (사이클) 이 존재하지 않는 그래프를 말한다.
• DAG는 여러 작업들 간의 상호 의존 관계등을 그래프로 표현할 때 흔하게 출현한다.

 

Reference

• 도서 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략