그래프 용어

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

  ㅇ 그래프 (Graph)  :  G
     - 정점 집합 (V)과 간선 집합 (E)의 순서쌍  :  G = (V,E)
        . V  :  정점 집합,  E  :  간선 집합

  ㅇ 정점/노드/마디/꼭짓점 (Vertex, Node)  :  V
     - 그래프를 구성하는 요소 중의 하나로써, 데이터가 저장되거나 연결이 시작/종료되는 지점

  ㅇ 간선/연결선/변/가지/선분 (Edge, Branch, Arc, Link)  :  E
     - 두 정점을 잇는 추상적 선분
        . 두 정점 간을 이어주며, 가중치를 갖는, 무향 또는 유향, 선분

     * 한편, (간선의 최대 개수)  (n : 정점 수)
        . 무향 그래프  :  n (n-1) / 2
        . 유향 그래프  :  n (n-1)

  ※ 例)  


2. 그래프 용어  :  "정점" 및 "간선의 속성" 간의 관계 (연결 특성)

  ㅇ 가중치 (Weight/Cost)
     - 간선에 수치(거리,비용,시간 등)를 부여한 것 
        . 가중치 그래프(Weighted Graph)를 형성함

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

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

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

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

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

  ㅇ 연결성 (Connectivity, Connected)
     - 모든 정점 쌍 사이에 최소 하나 이상의 경로가 존재하는 상태
        . 임의의 정점에서 다른 정점으로 가는 경로가 항상 존재하는 경우
     - 두 정점들 간에 경로(path)가 존재하면 연결되었다고 함


3. 그래프 용어  :  이동 및 경로 (Traverse & Path) 관련

  ㅇ 보행 (Walk)
     - 정점과 간선을 교대로 나열한 수열 (정점/간선 중복 허용)

  ㅇ 자취(트레일) (Trail)
     - 모든 간선이 서로 다른 보행 (정점은 중복 가능)
        . 중간에 어떤 간선도 2회 이상 사용 않는 경로

  ※ ☞ 경로 (Path) 참조
     - 경로  :  임의 경로는 일련의 간선들로 이루어짐
     - 경로 길이  :  경로를 구성하는 간선들의 가중치 합
     - 단순 경로  :  동일한 간선,정점을 중복 포함시키지 않는 경로
     - 순환 경로  :  시작 정점과 끝 정점이 같은 경로
     - 비순환적 경로  :  순환 경로가 없는 경우
     - 최단 경로  :  두 정점 간에 최소 경로 길이를 갖는 경로
     - 임계 경로  :  가장 긴 경로


4. 그래프 용어  :  방향 그래프에 한함

  ㅇ 입력, 출력
     - 방향 그래프에서, 들어옴(enter)을 말함
     - 방향 그래프에서, 나감(leave)을 말함

  ㅇ 입력 차수, 진입 차수 (In-degree) = 내차  :  in-d(v)
     - 방향 그래프에서 한 정점으로 들어오는 간선(화살표)의 수

  ㅇ 출력 차수, 진출 차수 (Out-degree) = 외차  :  out-d(v)
     - 방향 그래프에서 한 정점에서 나가는 간선(화살표)의 수

  ㅇ 전체 차수  :  {#d(v) = \text{in-d}(v) + \text{out-d}(v)#}
     - 이때, 차수는 입력 차수,출력 차수의 합  :  in-d(v) + out-d(v) = d(v)

  ㅇ 강한 연결 (Strongly Connected)
     - 유향 그래프에서, 모든 정점 쌍 {#(u, v)#}에 대해,
        . {#u \to v#} 경로와 {#v \to u#} 경로가 모두 존재할 때