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

(2020-08-20)

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

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

  ㅇ 연결선/변/가지/간선/선분 (Edge, Branch, Arc, Link)
     - 두 노드 간을 이어주는 선분

  ㅇ 차수 (Degree) : d(v)
     - 정점에 연결된 연결선/간선의 개수

     * 모든 정점차수의 합은 연결선의 수의 두 배
         
[# \sum_{v \in V} d(v) = 2 |E| #]
. 따라서, 모든 정점차수의 합은 짝수 ㅇ 입력, 출력, 입력 차수, 출력 차수 - 입력, 출력 . 방향 그래프에서, 들어옴(enter)을 말함 . 방향 그래프에서, 나감(leave)을 말함 - 입력 차수, 진입 차수 (In-degree) = 내차 . 방향 그래프에서 한 정점으로 들어오는 연결선의 수 - 출력 차수, 진출 차수 (Out-degree) = 외차 . 방향 그래프에서 한 정점에서 나가는 연결선의 수 ㅇ 인접 (Adjacency, Adjacent), 이웃 (Neighbor) ☞ 인접 관계 참조 - 연결선에 의해 직접 연결된 2개의 정점은, 서로 인접 관계(이웃 관계)에 있다고 말함 . 인접 관계의 표현 방법 : ☞ 인접 행렬, 인접 리스트 참조 - 인접한 꼭짓점 (Adjacent Vertices) : 연결된 두 정점을 말함 ㅇ 부속/근접 (Incident) - 정점간선이 연결되었을 때, 이 간선을 그 정점에 부속/근접되어 있다고 함 ㅇ 연결성 (Connectivity, Connected) - 두 정점들 간에 경로가 존재하면 연결되었다고 함 ㅇ 가중치 (Weight) - 연결선에 수치(비용 등)를 부여한 것 2. 그래프 용어 : 경로(Path) 관련 ㅇ 경로 (Path) - 어떤 정점 V(0)에서 시작하여 V(n)으로 끝나는 순회/방문/여정 . 두 정점 사이를 잇는 간선들을 순서대로 나열하게됨 (중간에 비면 안됨) ㅇ 경로 길이 (Path Length) - 두 정점 사이의 간선의 수 - 또는, 경로 상에 있는 각각의 간선들이 갖는 가중치들의 합 ㅇ 단순 경로 (Simple Path) - 임의 경로 상에 시작,끝 정점을 제외하고는 모든 정점들이 서로 다름 . 동일한 간선,노드를 중복 포함시키지 않음 . 같은 마디를 2 이상 거치지 않는 경로 - 한편, 방향 그래프일 경우에는, 단순 경로를 단순 방향 경로(Simple Directed Graph) 이라고 함 ㅇ 최단 경로 (Shortest Path) ☞ 최적 경로 참조 - 두 정점 간에 최소 경로 길이를 갖는 경로 . 단순 경로 이어야 함 - 사용 例) 최적화 문제 등 ㅇ 최단 길이 (Shortest Length) - 최단 경로의 길이 3. 그래프 용어 : 순환/비순환 경로(Path) 관련 ㅇ 순환 경로 (Cyclic Path) / 루프(Loop) / 사이클(Cycle) ☞ 루프순환 참조 - 자기 자신과 연결되는 정점으로, 순환적으로 이어지는 간선 또는 경로 . 경로의 시작점과 끝점이 같음 .. 시작과 끝이 같은 정점이 되는 단순 경로(simple path) . 경로에서 어떤 정점을 2번 이상 거치는 경우 - (a,a) 또는 < a,a > 형태의 연결선을 갖음 * 특히, . 싸이클이 없는 그래프를, 트리(Tree) 라고 함 . 자기자신을 연결하는 간선을, 자기 루프(Self Loop) 라고 함 ㅇ 순환적(Cyclic), 비순환적(Acyclic) - 순환적 : 그래프에 순환경로가 있는 경우를 말함 - 비순환적 : 그래프에 순환경로가 없는 경우를 말함 4. 그래프 용어 : 보행(Walk) 관련 ㅇ 보행 (Walk) - 반복을 허용하는 경로


[그래프 용어] 1. 그래프 용어 2. 노드, 가지 3. 루프 4. 인접관계

 
        최근수정     요약목록     참고문헌