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

(2021-10-12)

그래프 차수, 경로 , 경로 길이 , 단순 경로, 임계 경로, 순환 경로, 진입 차수, 진출 차수


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) ☞ 인접 관계(이웃 관계) 참조 - 특정 간선으로 연결된 두 정점의 관계 - 즉, 간선에 의해 직접 연결된 2개의 정점은, 서로 인접 관계(이웃 관계)에 있다고 말함 . 인접 관계의 표현 방법 : ☞ 인접 행렬, 인접 리스트 참조 - 인접한 꼭짓점 (Adjacent Vertices) : 연결된 두 정점을 말함 ㅇ 연결성 (Connectivity, Connected) - 두 정점들 간에 경로가 존재하면 연결되었다고 함 ㅇ 가중치 (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) - 반복을 허용하는 경로



Copyrightⓒ   차재복 (Cha Jae Bok)