그래프 종류

(2021-10-12)

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


1. 그래프 종류 : 방향 유무에 따른 분류

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

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


2. 그래프 종류 : 가중치 유무에 따른 분류

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

  ㅇ 비 가중치 그래프 (Non Weighted Graph)
     - 연결선에 가중치를 갖지 않는 그래프


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

  ㅇ 단순 그래프 (Simple Graph)
     - 임의의 두 정점 사이에 오직 1개 만의 연결선이 존재
        
     - 즉, 자기 순환(Self Loop), 다중 연결선(Parallel Edge)이 없음
     - 또한, 모든 경로가 자취(Trail : 중간에 어떤 연결선도 두 번 사용 안함)로 만 이루어진 그래프

  ㅇ 다중 그래프 (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)
     - 순환 그래프 : 순환경로가 있는 그래프
     - 비 순환 그래프 : 순환경로가 없는 그래프


4. 그래프 종류 : 응용 상의 분류방향성 비순환 그래프 (Directed Acyclic Graph, DAG)
     - 정점 간에(간선에) 방향은 있으나, 순환경로는 없는 그래프
        . 한 작업을 다른 작업 보다 우선 처리해야 하는 의존성을 모델링할 때 유용 함



Copyrightⓒ   차재복 (Cha Jae Bok)