그래프 용어

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

  ㅇ 그래프 (Graph)  :  G
     - 정점(V)과 연결선(E)의 집합  :  G = (V,E)

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

  ㅇ 연결선/변/가지/간선/선분 (Edge, Branch, Arc, Link)  :  E
     - 두 노드 간을 이어주는 선분
     - (연결선의 최대 개수) (n : 노드 수)
        . 무방향 그래프  :  n (n-1) /2
        . 방향 그래프    :  n (n-1)

  ※ 例)  

  ㅇ 차수 (Degree)  :  d(v)
     - 정점에 연결된 연결선/간선의 개수
        . 위 例) 그림에서, 정점 a,b,c의 차수는, d(a) = 2, d(b) = 3, d(c) = 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| #]
        . 즉, 모든 정점의 차수의 합은 짝수가 됨

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

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

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

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

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


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

  ※ ☞ 경로 (Path) 참조
     - 경로, 경로 길이, 자취(트레일), 단순 경로, 순환 경로, 비순환적 등


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

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

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

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

  ㅇ 이때, 차수는 입력 차수,출력 차수의 합  :  in-d(v) + out-d(v) = d(v) 


4. 그래프 용어  :  보행(Walk) 관련

  ㅇ 보행 (Walk)
     - 반복을 허용하는 경로