그래프가 무엇인지 알아보자

그래프

• 연결되어있는 객체간의 관계를 표현하는 자료구조
  
  
  
  

그래프의 역사

• 1800년 오일러에 의해 창안되었다.
  
  

• 오일러의 문제 : 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제

• 오일러의 정리 : 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가 존재한다.

• 오일러 정리에 의해 아래 그래프에는 오일러 경로가 존재하지 않는다.

그래프의 정의

• 그래프 $G$는 $(V,E)$로 표시한다.
  
  

• 정점 (Vertices)

  • 여러가지 특성을 가지는 객체를 의미한다.
  • $V(G)$ : 그래프 $G$의 정점들의 집합
  • 노드라고 부르기도 한다.

• 간선 (Edge)

  • 정점들 간의 관계를 의미한다.
  • $E(G)$ : 그래프 $G$의 간선들의 집합
  • 링크라고 부르기도 한다.

그래프의 표현

아래 예시 그래프를 이용하여 그래프를 표현해보자.

방법 1

$V(G1) \;=\; \{\,0,\;1,\;2,\;3\}$

$E(G1)\;=\;\{\;(0,\;1),\;(0,\;2),\;(0,\;3),\;(1,\;2),\;(2,\;3)\;\}$

방법 2

$V(G3)\;=\;\{\;0,\;1,\;2\;\}$

$E(G3)\;=\;\{\;<0,\;1>,\;<1,\;0>,\;<1,\;2>\;\}$