1. 그래프
그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.
객체는 노드로 표현되고 노드들은 간선(edge)으로 연결된다.
따라서 그래프는 노드와 각 노드를 연결하는 간선을 모아 놓은 것이다.
트리는 그래프의 대표적인 예시이다.
오일러 문제
-
오일러 문제: 다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제
이 때 위치는 정점(node)로, 다리는 간선으로 표현할 수 있다. -
오일러 정리: 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가 존재한다.
예를 들어 정점 A, B가 있을 때, 이것을 오일러 문제로 생각해보자.
A에서 출발하여 B에 도착한다면 간선 A->B를 한 번 사용한 것이다. 이 때, 다시 출발 장소인 A로 돌아와야 하기 때문에 간선 B->A가 필요하다. A의 입장에서 볼 때 B로 나가는 간선 1개가 있다면 필연적으로 B에서 A로 들어오는 간선 1개가 필요하다는 것을 알 수 있다.
다시 말해, 오일러 정리를 만족하려면 모든 정점은 해당 정점에서 나가고 들어오는 간선이 각각 짝을 이루는 형태로 존재해야 한다.
따라서 모든 정점에 연결된 간선의 수가 짝수일 때, 오일러 경로가 존재한다.
위 그림에서는 정점에 연결된 간선의 수가 홀수이므로 오일러 경로가 존재하지 않는다.
- 그래프 G는 (V, E)로 표시한다. G = (V, E)
- 정점(vertices) 또는 노드(node)
여러 가지 특성을 가질 수 있는 객체를 의미한다.
V(G): 그래프 G의 정점들의 집합 - 간선(edge) 또는 링크(link)
정점들 간의 관계를 의미한다.
E(G): 그래프 G의 간선들의 집합
2. 그래프의 종류
무방향 그래프(undirected graph)
두 정점을 연결하는 간선에 방향이 없는 그래프이다.
간선을 통해 양방향으로 갈 수 있다.
(A, B)로 표현한다.
방향 그래프(directed graph)
간선에 방향이 있는 그래프이다.
간선을 통해 한쪽 방향으로만 갈 수 있다.
<A, B>로 표현한다.
<A, B>와 <B, A>는 다르다.
가중치 그래프(weighted graph)
정점을 연결하는 간선에 가중치를 할당한 그래프이다.
- 네트워크(network)라고도 한다.
부분 그래프(subgraph)
기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프이다.
정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진다.
3. 그래프의 용어
-
인접 정점(adjacent vertex)
: 하나의 정점에서 간선에 의해 직접 연결된 정점 -
정점의 차수(degree)
: 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 -
진입 차수(in-degree)
: 방향 그래프에서 외부에서 오는 간선의 수 -
진출 차수(out-degree)
: 방향 그래프에서 외부로 나가는 간선의 수 -
그래프의 경로(path)
: 정점 vi에서 정점 vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트 -
그래프의 크기(size)
: 정점의 개수 -
단순 경로(simple path)
: 모두 다른 정점으로 구성된 경로 -
사이클(cycle)
: 시작 지점과 종료 지점이 동일한 경로 -
경로의 길이(length)
: 경로를 구성하는데 사용된 간선의 수 -
연결 그래프(connected graph)
: 그래프 내의 정점들이 최소한 하나의 경로로 연결된 상태
G2는 비연결 그래프이다. -
트리(tree)
: 사이클을 가지지 않는 연결 그래프 -
완전 그래프(complete graph)
: 모든 정점이 연결되어 있는 그래프
G2는 비연결 그래프이다.
4. 그래프의 표현 방법1 : 인접 행렬
if(간선(i, j)가 그래프에 존재){
M[i][j]=1 또는 true
}else{
M[i][j] = 0 또는 false
}인접 행렬의 대각선 성분은 정점 자신에서 자신을 가리키는 간선을 의미하기 때문에 모두 0이다.
-
무방향 그래프는 인접 행렬이 대칭이다.
5. 그래프의 표현 방법2: 인접 리스트
각 정점이 연결 리스트를 가지고 인접한 정점을 가리키도록 한다.
