Graph   그래프

1. 그래프(Graph) 이란?

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

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

  ㅇ [함수]  입출력 좌표의 순서쌍 집합을 좌표 상의 점들로 나타낸 그림
     - 함수의 성질이나 움직임 등이 잘 나타나 보임
        . 일변수 함수의 그래프 : 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. [이산수학]  그래프 참고사항

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

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

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

  ※ (특징)
     - 트리와 달리, 루트 노드가 없으므로, 통상, 시작 정점이 주어짐