그래프 종류

(2023-11-03)

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


1. [이산수학]  그래프 종류  :  방향 유무에 따른 분류

  ㅇ 무 방향 그래프 (Undirected Graph)
     - 정점 간에 방향성이 없음
        . 보통, 그래프하면 무방향 그래프를 지칭함
     - 두 정점 쌍(연결선)에 순서가 없음
        . (v,u) 및 (u,v)는 동일한 연결선
     - 例) 친밀 우호관계의 정도 표시 등
       
     - 특징  :  최대 간선 개수 = n (n-1) /2
        . (단, n : 정점 개수)

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


2. [이산수학]  그래프 종류  :  가중치 유무에 따른 분류

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

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


3. [이산수학]  그래프 종류  :  구조적 특징에 따른 분류

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

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

  ㅇ 의사 그래프 (Pseudo Graph)
     - 다중 연결선 및 자기 순환을 모두 허용하는 그래프
        

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

  ㅇ 부분 그래프 (Sub Graph)
     - 원래의 그래프에서 일부 노드,간선들을 제외하고 남은 그래프
        . 例) 트리 (Tree) 등
     - 최소 부분 그래프
        . 어떤 그래프에서 만들어진 부분 그래프들 중에서, 간선의 수가 가장 작은 것

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

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


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


5. [이산수학]  그래프 종류  :  그래프의 일종으로써의 트리트리 (tree) : 순환 루프를 포함하지 않는, 연결 그래프의 일종
     - 즉, 연결된 비순환 그래프
  ㅇ 숲 (forest) : 서로 중첩되는 부분이 없는 트리들의 집합을 
  ㅇ 신장 트리 (spanning tree) : 어떤 연결된 그래프에서, 노드 간 경로가 오직 하나 뿐
  ㅇ 신장 숲 (spanning forest) : 다수의 신장 트리들을 갖는 집합

그래프 종류
   1. 그래프 종류   2. 평면 그래프  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"