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. 평면 그래프
[그래프 용어] [그래프 알고리즘]

 
        요약목록     참고문헌