Graph   그래프

(2021-04-05)

그래프 이론

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

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. 그리스 수/문자

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

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