Graph   그래프

(2020-06-09)

그래프 이론

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

Top > [기술공통]
[기초과학]
[진동/파동]
[전기전자공학]
[방송/멀티미디어/정보이론]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
기술공통 > [공통/유사어(ㄱ~ㄹ)]
[공통/유사어 (ㅁ~ㅂ)]
[공통/유사어(ㅅ~ㅈ)]
[공통/유사어(ㅊ~ㅎ)]
[단순기술용어]
공통/유사어(ㄱ~ㄹ)   1. 가역적 (invertible,reciprocal,reversible)
  2. 개구 (aperture)
  3. 개체 (entity)
  4. 계층화 (layering,hierarchy)
  5. 구조 아키텍쳐 조직 매커니즘
  6. 그래프 (graph)
  7. 그리스 수/문자
  8. 데이터 (data)
  9. 도메인 (domain)
  10. 동차성 (homogeneity)
  11. 등시성 (isochronism)
  12. 레인징 (ranging)

1. 그래프(Graph) 이란?

  ㅇ [일반]  이해를 돕기위해 단순화시킨 그림

  ㅇ [통계자료표현]  통계 자료들을 일목요연하게 정리,분석하여 보여주기 위해 도형화시킨 그림
     - 例) x-y plot(면 그래프), polar plot(극좌표 그래프), surface plot(3 차원 표면 그래프)
     - 例) pie chart(파이 챠트), bar graph(막대 그래프), histogram(히스토그램) 등

  ㅇ [함수]  입출력 좌표순서쌍 집합좌표 상의 점들로 나타낸 그림
     - 함수의 성질이나 움직임 등이 잘 나타나 보임
        . 일변수 함수의 그래프 : y=f(x)인 곡선(C)
        . 이변수 함수의 그래프 : z=f(x,y)의 곡면(S)

  ㅇ [컴퓨터:이산수학,자료구조 등]
     - 기하학적인 도형,구조,방정식,알고리즘 등을 설명하기 위한 시각적 표현 도구
        . 선분에 의해 연결된 유한개 점들의 집합
     - 특징
        . 현실 세계의 복잡 다양함에 대해 간략화를 통해 중요한 부분 만을 시각화/모델링에 효과적임
        . 꽤 일반적인 연결 관계의 표현이 가능 (인간관계,노선도,네트워크 등)
        . 선형 자료구조,트리 자료구조로는 표현하기 어려운 다대다(多:多) 관계 표현이 용이함


2. [이산수학]  그래프 이론의 기원

  ㅇ 18세기 쾨니스버스 시의 7개 섬을 잇는 다리를, 
     - 한번씩 건너면서 같은 곳으로 돌아올 수 있는가?에 대한
     - 수학오일러의 문제 해결에서 시작됨

  ㅇ 여기서, 임의 두 지역(정점) 간에 다리의 수 만이 중요함                ☞ 평면 그래프 참조
     - 즉, 홀수 개의 다리를 갖는 지역(정점) 수가 0 또는 2개 (짝수)이어야 함을 오일러증명함

  ※ 결국, 다음 질문들을 아우르는 모델링 도구로써, `그래프 이론`를 사용하게 됨
     - 어떤 항목까지 가는 경로가 있는가?
     - 가장 짧은 최단 경로는 무엇인가?, 
     - 어떤 항목의 다음 항목들이 얼마나 많은가? 등등 


3. [이산수학]  그래프의 정의 

  ㅇ 유한개의 `정점집합 V`와 `연결선의 집합 E`으로 그려지는 집합

  ㅇ 표기 :  G = (V,E)
     - G : 하나의 그래프
     - V : 1 이상의 정점(Vertex)의 집합 
     - E : 두 정점 쌍을 이어주는 연결선/간선/(Edge)의 집합

  ㅇ 例)
     


4. [이산수학]  그래프의 표현 

  ㅇ [기초 표현]  그림으로 나타냄
  ㅇ [기호 표현]  정점들의 관계를 나타내는 연결선들의 집합으로 표현 : G = (V,E)
  ㅇ [행렬 표현]  인접 행렬 (Adjacency Matrix)
  ㅇ [자료구조 표현]  인접 리스트 (Adjaency List)


5. [이산수학/자료구조]  그래프의 연산 종류

  ㅇ 그래프 생성
  ㅇ 그래프 삭제
  ㅇ 노드 추가
  ㅇ 노드 제거
  ㅇ 간선 추가
  ㅇ 간선 제거
  ㅇ 인접 노드 반환 등


6. [이산수학]  그래프 참고사항

  ※ ☞ 그래프 용어 (정점, 연결선, 차수, 경로, 인접, 부속 등) 참조

  ※ ☞ 그래프 종류 (방향 그래프, 가중치 그래프, 연결 그래프, 완전 그래프 등) 참조

  ※ ☞ 그래프 알고리즘 (그래프 순회, 신장 트리 작성, 최단 경로 등) 참조


[그래프] 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.   기술경영

 
        요약목록     참고문헌