그래프 용어

(2022-08-13)

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


1. 그래프 용어  :  주요 용어정점/꼭짓점/노드/마디 (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(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) 참조 - 경로 길이, 자취, 단순 경로, 순환 경로 등 3. 그래프 용어 : 방향 그래프에 한함 ㅇ 입력, 출력 - 방향 그래프에서, 들어옴(enter)을 말함 - 방향 그래프에서, 나감(leave)을 말함 ㅇ 입력 차수, 진입 차수 (In-degree) = 내차 - 방향 그래프에서 한 정점으로 들어오는 연결선의 수 ㅇ 출력 차수, 진출 차수 (Out-degree) = 외차 - 방향 그래프에서 한 정점에서 나가는 연결선의 수 4. 그래프 용어 : 보행(Walk) 관련 ㅇ 보행 (Walk) - 반복을 허용하는 경로



"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"