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

(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. 인접관계
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (그래프,트리)
          1.   그래프
                1. 그래프
                2. 그래프 종류
                3. 그래프 표현
                4. 평면 그래프
            1.   그래프 용어
            2.   그래프 알고리즘
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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