그래프 종류

(2018-07-03)

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

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

  ㅇ 무방향 그래프  (undirected graph)
     - 두 정점 쌍(연결선)에 순서가 없음
        . (v,u) 및 (u,v)는 동일한 연결선
     - 보통 그래프하면 무방향 그래프를 지칭함
       

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

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


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

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

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

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

  ㅇ 완전 그래프 (Complete Graph)
     - 모든 정점끼리 모두가 연결선으로 연결된 그래프 
        . n개의 정점에서 최다 연결선의 수가 n(n-1)/2인 그래프
       
     - 모든 정점 쌍 간에 연결선이 반드시 존재

  ㅇ 연결 그래프 (Connected Graph)
     - 모든 정점들이 연결되어 있는 그래프
        . 두 정점 간에 최소 1 이상의 경로가 반드시 있게되는 그래프

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


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

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