1. 그래프 용어 : 주요 용어
ㅇ 정점/꼭짓점/노드/마디 (Vertex, Node)
- 그래프를 구성하는 요소중의 하나로 연결점
ㅇ 연결선/변/가지/간선/선분 (Edge, Branch, Arc, Link)
- 두 노드 간을 이어주는 선분
ㅇ 차수 (Degree) : d(v)
- 정점에 연결된 연결선/간선의 개수
* 모든 정점의 차수의 합은 연결선의 수의 두 배
[# \sum_{v \in V} d(v) = 2 |E| #]
. 따라서, 모든 정점의 차수의 합은 짝수
* 입력, 출력, 입력 차수, 출력 차수 ☞ 아래 4.항(그래프 용어 : 방향 그래프에 한함) 참조
ㅇ 부속/근접/결합 (Incident)
- 두 정점(정점 쌍)에 하나의 간선이 연결되었을 때,
- 이 간선을 그 정점에 부속/근접/결합되어 있다(incident on) 라고 함
ㅇ 인접 (Adjacency, Adjacent), 이웃 (Neighbor) ☞ 인접 관계(이웃 관계) 참조
- 특정 간선으로 연결된 두 정점의 관계
- 즉, 간선에 의해 직접 연결된 2개의 정점은, 서로 인접 관계(이웃 관계)에 있다고 말함
. 인접 관계의 표현 방법 : ☞ 인접 행렬, 인접 리스트 참조
- 인접한 꼭짓점 (Adjacent Vertices) : 연결된 두 정점을 말함
ㅇ 연결성 (Connectivity, Connected)
- 두 정점들 간에 경로가 존재하면 연결되었다고 함
ㅇ 가중치 (Weight)
- 연결선에 수치(비용 등)를 부여한 것
2. 그래프 용어 : 경로(Path) 관련
ㅇ 경로 (Path)
- 어떤 정점 V(0)에서 시작하여 V(n)으로 끝나는 순회/방문/여정
- 경로 표현 : 두 정점 사이를 잇는 정점 또는 간선들을 순서대로 나열하게됨 (중간에 비면 안됨)
ㅇ 경로 길이 (Path Length)
- 두 정점 사이의 간선의 수
- 또는, 경로 상에 있는 각각의 간선들이 갖는 가중치들의 합
ㅇ 단순 경로 (Simple Path)
- 임의 경로 상에 시작,끝 정점을 제외하고는 모든 정점들이 서로 다름
. 동일한 간선,노드를 중복 포함시키지 않음
. 같은 마디를 2 이상 거치지 않는 경로
- 한편, 방향 그래프일 경우에는, 단순 경로를 단순 방향 경로(Simple Directed Graph) 이라고 함
ㅇ 임계 경로 (Critical Path)
- 모든 가능한 경로 중 가중치 합이 최대가 되는 경로 (가장 긴 경로)
. 예로써, 작업 공정 그래프에서, 전체 작업을 끝내는 데 필요한 최소 시간 = 임계 경로의 길이
. 따라서, 임계 경로 상에 있는 작업들에 집중하면 전체 작업을 더 빨리 끝낼 수 있게 됨
ㅇ 최단 경로 (Shortest Path) ☞ 최적 경로 참조
- 두 정점 간에 최소 경로 길이를 갖는 경로
. 단순 경로 이어야 함
- 사용 例) 최적화 문제 등
ㅇ 최단 길이 (Shortest Length)
- 최단 경로의 길이
3. 그래프 용어 : 순환/비순환 경로(Path) 관련
ㅇ 순환 경로 (Cyclic Path) / 루프 (Loop) / 사이클 (Cycle) ☞ 루프순환 참조
- 자기 자신과 연결되는 정점으로, 순환적으로 이어지는 간선 또는 경로
. 경로의 시작점과 끝점이 같음
.. 시작과 끝이 같은 정점이 되는 단순 경로(simple path)
. 경로에서 어떤 정점을 2번 이상 거치는 경우
- (a,a) 또는 < a,a > 형태의 연결선을 갖음
* 특히,
. 싸이클이 없는 그래프를, 트리(Tree) 또는 방향 비순환 그래프(DAG) 라고 함
. 자기자신을 연결(시작,끝이 자기자신)하는 간선을, 자기 루프(Self Loop) 라고 함
ㅇ 순환적(Cyclic), 비순환적(Acyclic)
- 순환적 : 그래프에 순환경로가 있는 경우를 말함
- 비순환적 : 그래프에 순환경로가 없는 경우를 말함
4. 그래프 용어 : 방향 그래프에 한함
ㅇ 입력, 출력
- 방향 그래프에서, 들어옴(enter)을 말함
- 방향 그래프에서, 나감(leave)을 말함
ㅇ 입력 차수, 진입 차수 (In-degree) = 내차
- 방향 그래프에서 한 정점으로 들어오는 연결선의 수
ㅇ 출력 차수, 진출 차수 (Out-degree) = 외차
- 방향 그래프에서 한 정점에서 나가는 연결선의 수
5. 그래프 용어 : 보행(Walk) 관련
ㅇ 보행 (Walk)
- 반복을 허용하는 경로