[알고리즘] 그래프 1 - 그래프의 개념

목차

그래프의 개념

그래프는 원소 사이의 다대다 n:n 관계를 표현하는 비선형 자료구조이다. 예를 들어 지하철 노선도나 버스 노선도를 보면 선형 자료구조로는 표현할 수가 없기 때문이다. 그래프는 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 Edge의 집합으로 구성된다.

그래프 G는 G=(V, E)로 정의하는데, V는 그래프에 있는 정점의 집합을 뜻하고 E는 정점을 연결하는 간선의 집합을 뜻한다.

그래프의 예

그래프의 종류

무방향 그래프

무방향 그래프 Undirected Graph는 두 정점을 연결하는 간선에 방향이 없는 그래프인데, 무방향 그래프에서 정점 Va와 Vb를 연결하는 간선을 (Va, Vb)로 표현하고 각 정점에서는 (Va, Vb) 또는 (Vb, Va)처럼 간선을 나타낸다.

위에 사진이 무방향 그래프의 예이다. 

 

방향 그래프

방향 그래프 Directed Graph는 간선에 방향이 있는 그래프로서 Digraph라고도 하며 방향 그래프에서 정점 Va에서 정점 Vb를 연결하는 간선, 즉 Va -> Vb,  Va-> Vc는 <Va , Vb>  <Va, Vc>처럼 표현하고 화살표로 나타낸다.

여기서 Va는 꼬리 Tail, Vb와 Vc를 머리 Head라고하며 각각 서로 다른 간선으로 취급한다.

완전 그래프

말 그대로 각 정점에서 모든 정점이 연결되어 있어 최대로 많은 간선 수를 가진 그래프가 된다.

이때 무방향 그래프에서는 정점이 n개라면 최대 간선 수가 n(n - 1) / 2개가 되며, 방향 그래프에서는 두 정점에 대해 방향이 다른 간선을 2개씩 연결할 수 있어 최대 간선 수는 무방향 그래프보다 2배 많은 n(n - 1) 개가 된다.

부분 그래프

원래 그래프에서 정점이나 간선을 일부만 놔두어 만든 그래프를 부분sub 그래프라 한다.

가중 그래프

정점을 연결하는 간선에 가중치 Weight를 지정한 그래프로 가중치 그래프 Weight Graph 또는 네트워크 Network라 한다.

그래프에 관련된 용어들

1. 인접 (Adjacent):
   • 그래프에서 두 노드가 간선으로 직접 연결되어 있는 상태를 나타낸다.
   • 무방향 그래프에서는 인접한 개념이 대칭적이지만, 방향 그래프에서는 방향에 따라 다를 수 있다.
2. 부속 (Incident):
   • 간선이 노드에 속해 있는 상태를 나타냅니다. 한 노드에 인접한 간선들은 해당 노드에 부속되어 있다고 말할 수 있다..
3. 경로 길이 (Path Length):
   • 그래프에서 두 노드 간의 경로에 포함된 간선의 수를 나타낸다.
4. 단순 경로 (Simple Path):
   • 경로 중에서 반복되는 노드가 없는 경로를 말한다.
5. 사이클 (Cycle):
   • 한 노드에서 시작하여 다시 같은 노드로 돌아오는 닫힌 경로를 가진 그래프를 사이클이라고 한다.
   • 무방향 그래프에서는 단순 사이클이라는 용어가 사용된다.
6. DAG (Directed Acyclic Graph):
   • 방향 그래프 중에서 순환 경로가 없는 그래프를 DAG라고 한다.
   • DAG는 위상 정렬 등의 작업에 유용하게 활용한다.
7. 연결 (Connected):
   • 무방향 그래프에서 모든 노드 간에 최소한 하나의 경로가 존재하는 경우, 해당 그래프는 연결되었다고 한다.
8. 연결 그래프 (Connected Graph):
   • 그래프에서 모든 노드 간에 경로가 존재하는 경우를 나타낸다.
9. 단절 그래프 (Disconnected Graph):
   • 최소한 하나의 노드에 대해 다른 노드로의 경로가 없는 경우, 해당 그래프는 단절되었다고 한다.