1. 그래프 용어 : 경로(Path) 관련
ㅇ 경로 (Path)
- 어떤 정점 V(0)에서 시작하여 V(n)으로 끝나는 순회/방문/여정
- 경로 표현 : 두 정점 사이를 잇는 정점 또는 간선들을 순서대로 나열하게됨 (중간에 비면 안됨)
ㅇ 자취, 트레일 (Trail)
- 중간에 어떤 연결선도 2회 이상 사용 않는 경로
- 자취 표현 : 두 정점 사이를 연결선으로만 순서대로 나열하면 됨 (연결선 반복 사용하면 안됨)
ㅇ 경로 길이 (Path Length)
- 두 정점 사이의 간선의 수
- 또는, 경로 상에 있는 각각의 간선들이 갖는 가중치들의 합
2. 그래프 용어 : 단순, 임계, 최단 경로(Path) 관련
ㅇ 단순 경로 (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)
- 순환적 : 그래프에 순환경로가 있는 경우를 말함
- 비순환적 : 그래프에 순환경로가 없는 경우를 말함