그래프 종류

(2020-03-17)

Directed Graph, 방향 그래프, Weighted Graph, 가중치 그래프, Connected Graph, 연결 그래프, Complete Graph, 완전 그래프

1. 그래프 종류 : 방향,가중치에 따른 분류

  ㅇ 무 방향 그래프  (undirected graph)
     - 두 정점 쌍(연결선)에 순서가 없음
        . (v,u) 및 (u,v)는 동일한 연결선
     - 보통, 그래프하면 무방향 그래프를 지칭함
     - 例) 항공 노선도, 친밀 우호관계 등
       

  ㅇ 방향 그래프 (directed graph,digraph) 
     - 두 정점 쌍(연결선)에 순서가 있음 (순서쌍)
        . < v,u > 및 < u,v >는 서로 다른 연결선 
     - 정점 간에 방향성 있는 연결선
     - 정점 간에 함수적 관계성을 표현하는데 편리함
     - 例) 네트워크 경로 (Route) 등
       

  ㅇ 가중치 그래프 (Weighted Graph)
     - 연결선에 숫자(가중치)를 갖는 그래프
        . 경로 길이 = 경로 상에 있는 연결선들이 갖는 가중치들의 합


2. 그래프 종류 : 구조적 특징에 따른 분류

  ㅇ 단순 그래프 (simple graph)
     - 임의의 두 정점 사이에 오직 1개 만의 연결선이 존재
        

  ㅇ 다중 그래프 (multiple graph)
     - 임의의 두 정점 사이에 2 이상의 다중 연결선이 존재
        

  ㅇ 의사 그래프 (pseudo graph)
     - 다중 연결선 및 루프를 허용하는 그래프
        

  ㅇ 완전 그래프 (Complete Graph) 또는 연결 그래프 (Connected Graph)
     - 모든 정점끼리 연결된 그래프
        . 두 정점 간에 최소 1 이상의 경로가 반드시 있게되는 그래프
        . 모든 정점 쌍 간에 연결선이 반드시 존재
     - 연결선의 수 : n개의 정점에서, n(n-1)/2
         

  ㅇ 부분 그래프 (Sub Graph)
     - 원래의 그래프에서 일부 노드,간선들을 제외하고 남은 그래프

  ㅇ 밀집 그래프 (Dense Graph), 희소 그래프 (Sparse Graph)
     - 밀집 그래프 : 간선의 수가 최대 간선의 수에 가까운 그래프
     - 희소 그래프 : 간선이 얼마 없는 그래프

  ㅇ 순환 그래프(Cyclical Graph), 비 순환 그래프(Acyclical Graph)
     - 순환 그래프 : 순환경로가 있는 그래프
     - 비 순환 그래프 : 순환경로가 없는 그래프


[그래프] 1. 그래프 2. 그래프 종류 3. 그래프 표현
[그래프 용어] [그래프 알고리즘]

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