그래프 용어

(2023-11-16)

그래프 차수, 진입 차수, 진출 차수


1. 그래프 용어  :  주요 용어그래프 (Graph)  :  G
     - 정점(V)과 연결선(E)의 집합  :  G = (V,E)

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

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

  ※ 例)  차수 (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) - 반복을 허용하는 경로

그래프 용어
   1. 그래프 용어   2. 노드, 가지   3. 가지 종류   4. 인접   5. 차수   6. 경로   7. 루프  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"