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

(2020-02-20)

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

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

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

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

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

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

  ㅇ 인접 (Adjacency,Adjacent)                                              ☞ 인접 관계 참조
     - 연결선에 의해 직접 연결된 2개의 정점은, 서로 인접 관계에 있다고 말함
        . 인접 관계의 표현                                     ☞ 인접 행렬, 인접 리스트 참조
     - 인접한 꼭짓점 (Adjacent Vertices) : 연결된 두 정점

  ㅇ 부속 (Incident)
     - 두 정점 간에 간선이 연결되었을 때, 이 간선을 두 정점에 부속되어 있다고 함

  ㅇ 연결성 (Connectivity,Connected)
     - 두 정점들 간에 경로가 존재하면 연결되었다고 함


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

  ㅇ 경로 (Path)
     - 어떤 정점 V(0)에서 시작하여 V(n)으로 끝나는 순회/방문/여정
        . 두 정점 사이를 잇는 간선들을 순서대로 나열하게됨 (중간에 비면 안됨)

  ㅇ 경로 길이 (Path Length)
     - 두 정점 사이의 간선의 수
     - 또는, 경로 상에 있는 각각의 간선들이 갖는 가중치들의 합

  ㅇ 단순 경로 (Simple Path)
     - 임의 경로 상에 시작,끝 정점을 제외하고는 모든 정점들이 서로 다름
        . 동일한 간선,노드를 중복 포함시키지 않음
        . 같은 마디를 2 이상 거치지 않는 경로
     - 한편, 방향 그래프일 경우에는, 단순 경로를 단순 방향 경로(Simple Directed Graph) 이라고 함

  ㅇ 최단 경로 (Shortest Path)
     - 두 정점 간에 최소 경로 길이를 갖는 경로
        . 단순 경로 이어야 함
     - 사용 例) 최적화 문제 등

  ㅇ 최단 길이 (Shortest Length)
     - 최단 경로의 길이

  ㅇ 루프(Loop) / 사이클(Cycle) / 순환경로                                      ☞ 루프순환 참조
     - 자기 자신과 연결되는 정점으로, 순환적으로 이어지는 간선 또는 경로
        . 경로의 시작점과 끝점이 같음
           .. 시작과 끝이 같은 정점이 되는 단순 경로(simple path)
        . 경로에서 어떤 정점을 2번 이상 거치는 경우
     - (a,a) 또는 < a,a > 형태의 연결선을 갖음

     * 특히, 
        . 싸이클이 없는 그래프를, 트리(Tree) 라고 함
        . 자기자신을 연결하는 간선을, 자기 루프(Self Loop) 라고 함

  ㅇ 순환적(Cyclic), 비순환적(Acyclic)
     - 순환적 : 그래프에 순환경로가 있는 경우를 말함
     - 비순환적 : 그래프에 순환경로가 없는 경우를 말함


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

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