Path   경로

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)
     - 순환적 : 그래프에 순환경로가 있는 경우를 말함
     - 비순환적 : 그래프에 순환경로가 없는 경우를 말함