1. [이산수학] 그래프 종류 : 방향 유무에 따른 분류
ㅇ 무 방향 그래프 (Undirected Graph)
- 정점 간에 방향성이 없음
. 보통, 그래프하면 무방향 그래프를 지칭함
- 두 정점 쌍(연결선)에 순서가 없음
. (v,u) 및 (u,v)는 동일한 연결선
- 例) 친밀 우호관계의 정도 표시 등
- 특징 : 최대 간선 개수 = n (n-1) /2
. (단, n : 정점 개수)
ㅇ 방향 그래프 (Directed Graph, Digraph)
- 정점 간에 방향성이 있음
. 정점 간에 함수적 관계성 등을 표현하는데 편리함
- 두 정점 쌍(연결선)에 순서가 있음 (순서쌍)
. < v,u > 및 < u,v >는 서로 다른 연결선
- 例) 방향성을 지닌 네트워크 경로 (Route) 등
- 특징 : 최대 간선 개수 = n (n-1)
2. [이산수학] 그래프 종류 : 가중치 유무에 따른 분류
ㅇ 가중치 그래프 (Weighted Graph)
- 연결선에 가중치를 갖는 그래프
. 경로 길이 = 경로 상에 있는 연결선들이 갖는 가중치들의 합
- 例) 트래픽 경중 있는 네트워크 등
ㅇ 비 가중치 그래프 (Non Weighted Graph)
- 연결선에 가중치를 갖지 않는 그래프
3. [이산수학] 그래프 종류 : 구조적 특징에 따른 분류
ㅇ 단순 그래프 (Simple Graph)
- 임의의 두 정점 사이에 오직 1개 만의 연결선이 존재
- 특징
. 자기 순환(Self Loop), 다중 연결선(Parallel Edge)이 없음
. 모든 경로가 자취(Trail : 중간에 어떤 연결선도 두 번 사용 안함)로 만 이루어진 그래프
ㅇ 다중 그래프 (Multiple Graph)
- 임의의 두 정점 사이에 2 이상의 다중 연결선(Parallel Edge)이 존재
ㅇ 의사 그래프 (Pseudo Graph)
- 다중 연결선 및 자기 순환을 모두 허용하는 그래프
ㅇ 완전 그래프 (Complete Graph), 때론, 연결 그래프 (Connected Graph)
- 모든 정점끼리 연결된 그래프
. 두 정점 간에 최소 1 이상의 경로가 반드시 있게되는 그래프
. 모든 정점 쌍 간에 연결선이 반드시 존재
- 연결선의 수 : n개의 정점에서, n(n-1)/2
ㅇ 부분 그래프 (Sub Graph)
- 원래의 그래프에서 일부 노드,간선들을 제외하고 남은 그래프
. 例) 트리 (Tree) 등
- 최소 부분 그래프
. 어떤 그래프에서 만들어진 부분 그래프들 중에서, 간선의 수가 가장 작은 것
ㅇ 밀집 그래프 (Dense Graph), 희소 그래프 (Sparse Graph)
- 밀집 그래프 : 간선의 수가 최대 간선의 수에 가까운 그래프
- 희소 그래프 : 간선이 얼마 없는 그래프
ㅇ 순환 그래프(Cyclical Graph), 비 순환 그래프(Acyclical Graph)
- 순환 그래프 : 순환경로가 있는 그래프
- 비 순환 그래프 : 순환경로가 없는 그래프
4. [이산수학] 그래프 종류 : 응용 상의 분류
ㅇ 방향성 비순환 그래프 (Directed Acyclic Graph, DAG)
- 정점 간에(간선에) 방향은 있으나, 순환경로는 없는 그래프
. 한 작업을 다른 작업 보다 우선 처리해야 하는 의존성을 모델링할 때 유용 함
5. [이산수학] 그래프 종류 : 그래프의 일종으로써의 트리
ㅇ 트리 (tree) : 순환 루프를 포함하지 않는, 연결 그래프의 일종
- 즉, 연결된 비순환 그래프
ㅇ 숲 (forest) : 서로 중첩되는 부분이 없는 트리들의 집합을
ㅇ 신장 트리 (spanning tree) : 어떤 연결된 그래프에서, 노드 간 경로가 오직 하나 뿐
ㅇ 신장 숲 (spanning forest) : 다수의 신장 트리들을 갖는 집합