그래프 용어, 그래프 관련 주요 용어

1. 그래프 용어 : 주요 용어

  ㅇ 정점/꼭짓점/노드/마디 (Vertex, Node)  :  V
     - 그래프를 구성하는 요소중의 하나로 연결점

  ㅇ 연결선/변/가지/간선/선분 (Edge, Branch, Arc, Link)  :  E
     - 두 노드 간을 이어주는 선분

  ※ 例)  

  ㅇ 차수 (Degree)  :  d(v)
     - 정점에 연결된 연결선/간선의 개수
        . 위 例) 그림에서, 정점 a,b,c의 차수는, d(a) = 2, d(b) = 3, d(b) = 1 

     * 모든 정점의 차수의 합은 연결선의 수의 두 배
        . 위 例) 그림에서, d(a) + d(b) + d(c) = 2 + 3 + 1 = 6 (연결선 x 2 = 3 x 2 = 6)
         
[# \sum_{v \in V} d(v) = 2 |E| #]
        . 즉, 모든 정점의 차수의 합은 짝수가 됨

     * 입력, 출력, 입력 차수, 출력 차수     ☞ 아래 4.항(그래프 용어 : 방향 그래프에 한함) 참조

  ㅇ 부속/근접/결합 (Incident)
     - 두 정점(정점 쌍)에 하나의 간선이 연결되었을 때,
     - 이 간선을 그 정점에 부속/근접/결합되어 있다(incident on) 라고 함

  ㅇ 인접 (Adjacency, Adjacent), 이웃 (Neighbor)                   ☞ 인접 관계(이웃 관계) 참조
     - 특정 간선으로 연결된 두 정점의 관계
        . 위 例) 그림에서, a,b 및 b,c는 인접 관계에 있고, a,c는 그렇지 못함
     - 즉, 간선에 의해 직접 연결된 2개의 정점은, 서로 인접 관계(이웃 관계)에 있다고 말함
        . 인접 관계의 표현 방법 : ☞ 인접 행렬, 인접 리스트 참조
     - 인접한 꼭짓점 (Adjacent Vertices) : 연결된 두 정점을 말함

  ㅇ 연결성 (Connectivity, Connected)
     - 두 정점들 간에 경로(path)가 존재하면 연결되었다고 함

  ㅇ 가중치 (Weight)
     - 연결선에 수치(비용 등)를 부여한 것 


2. 그래프 용어 : 경로(Path) 관련

  ㅇ 경로 (Path)
     - 어떤 정점 V(0)에서 시작하여 V(n)으로 끝나는 순회/방문/여정
     - 경로 표현 : 두 정점 사이를 잇는 정점 또는 간선들을 순서대로 나열하게됨 (중간에 비면 안됨)

  ㅇ 자취, 트레일 (Trail)
     - 중간에 어떤 연결선도 2회 이상 사용 않는 경로
     - 자취 표현 : 두 정점 사이를 연결선으로만 순서대로 나열하면 됨 (연결선 반복 사용하면 안됨)

  ㅇ 경로 길이 (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)
     - 반복을 허용하는 경로