Graph   그래프

(2021-04-05)

그래프 이론

Top > [기술공통]
[기초과학]
[진동/파동]
[전기전자공학]
[방송/멀티미디어/정보이론]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
기술공통 > [공통/유사어(ㄱ~ㄴ)]
[공통/유사어(ㄷ~ㄹ)]
[공통/유사어 (ㅁ~ㅂ)]
[공통/유사어(ㅅ)]
[공통/유사어(ㅇ~ㅈ)]
[공통/유사어(ㅊ~ㅌ)]
[공통/유사어(ㅍ~ㅎ)]
[단순기술용어]
공통/유사어(ㄱ~ㄴ)   1. 가역적 (invertible,reciprocal,reversible)
  2. 감쇠 (attenuation,loss,damping,decay)
  3. 개구 (aperture)
  4. 개체 (entity)
  5. 격자(lattice,grating,grid)
  6. 계층화 (layering,hierarchy)
  7. 공간 (space)
  8. 구조 아키텍쳐 조직 매커니즘
  9. 그래프 (graph)
  10. 그리스 수/문자

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

1. 그래프(Graph) 이란?

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

  ㅇ [통계자료표현]  통계 자료들을 일목요연하게 정리,분석하여 보여주기 위해 도형화시킨 그림
     - 수치형 그래프 : 막대 그래프, 꺽은선 그래프 등
     - 비율형 그래프 : 띠 그래프, 원 그래프 등
     - 분포형 그래프 : 도수분포표, 히스토그램 등
     - 관계형 그래프 : 산점도 등 

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

  ㅇ [응용 과학 : 컴퓨터(이산수학,자료구조) 등]
     - 용도
        . 기하학적인 도형,구조,방정식,알고리즘의 설명,해석 등
        . 특히, 시각적으로 단순화시킨 표현 및 모델화에 유용한 도구
     - 특징
        . 현실 세계의 복잡 다양함에 대해 간략화를 통해 중요한 부분 만을 시각화/모델링에 효과적임
        . 그래프의 모양이 아닌 정점들 간에 직접적인 연결성의 존재 유무에 만 관심을 둠
        . 꽤 일반적인 연결 관계의 표현이 가능 (인간관계,노선도,네트워크 등)
        . 선형 자료구조로는 표현하기 어려운 다대다(多:多) 관계 표현이 용이함


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

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

  ㅇ 여기서, 임의 두 지역(정점) 간에 연결된 다리의 수 만이 중요함             ☞ 평면 그래프 참조
     - 당시, 모든 정점(지역)의 차수(연결된 다리의 수)가 짝수이어야 함을 오일러가 해결 제시하고,
     - 후에, 1873년 Cart Hierholzer가 이를 수학적으로 증명 함 

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


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

  ㅇ 유한개의 `정점집합 V`와 `연결선의 집합 E`으로 그려지는 집합
     - 선분에 의해 연결된 유한개 점들의 집합

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

  ㅇ 例)
     


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

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


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

  ㅇ 그래프 생성 : create_graph()
  ㅇ 그래프 초기화 : init_graph(g)
  ㅇ 정점 추가 : insert_vertex(g,v)
  ㅇ 정점 제거 : delete_vertex(g,v)
  ㅇ 간선 추가 : insert_edge(g,u,v)
  ㅇ 간선 제거 : delete_edge(g,u,v)
  ㅇ 공백 그래프 여부 : is_empty(g)
  ㅇ 그래프 제거 : destroy_graph(g)
  ㅇ 인접 정점 반환 : adjacent(g,v)


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

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

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

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


[공통/유사어(ㄱ~ㄴ)] 1. 가역적 (invertible,reciprocal,reversible) 2. 감쇠 (attenuation,loss,damping,decay) 3. 개구 (aperture) 4. 개체 (entity) 5. 격자(lattice,grating,grid) 6. 계층화 (layering,hierarchy) 7. 공간 (space) 8. 구조 아키텍쳐 조직 매커니즘 9. 그래프 (graph) 10. 그리스 수/문자
  1.   기술공통
    1.   공통/유사어(ㄱ~ㄴ)
      1.   1. 가역적 (invertible,reciprocal,reversible)
          2. 감쇠 (attenuation,loss,damping,decay)
          3. 개구 (aperture)
          4. 개체 (entity)
          5. 격자(lattice,grating,grid)
          6. 계층화 (layering,hierarchy)
          7. 공간 (space)
          8. 구조 아키텍쳐 조직 매커니즘
          9. 그래프 (graph)
          10. 그리스 수/문자
    2.   공통/유사어(ㄷ~ㄹ)
    3.   공통/유사어 (ㅁ~ㅂ)
    4.   공통/유사어(ㅅ)
    5.   공통/유사어(ㅇ~ㅈ)
    6.   공통/유사어(ㅊ~ㅌ)
    7.   공통/유사어(ㅍ~ㅎ)
    8.   단순기술용어
  2.   기초과학
  3.   진동/파동
  4.   전기전자공학
  5.   방송/멀티미디어/정보이론
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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