그래프 이론

1 개념

graph theory

graph理論

그래프 이론

• 자연이나 사회 현상, 네트워크의 구조를 점과 선으로 단순화해 이해하고 분석하려는 이론
• 최근 다양한 분야에 응용하면서 중요도가 높아지고 있음
• 18세기경, 한붓그리기 문제로 유명한 쾨니히스베르크의 다리에서 그래프 이론이 시작됨

※ 쾨니히스베르크의 다리는 한붓그리기가 안됨

 

▲쾨니히스베르크의 다리

2 내용

• 점은 정점(ver-tex)
• 정점을 연결하는 선을 간선(edge)
• 정점과 간선을 건너뛰지 않고 움직이는 것을 워크(walk)
• 간선이 중복되지 않는 워크를 트레일(trail)
• 모든 간선을 지나가는 트레일을 오일러 트레일(Euler trail)이라 함

3 오일러 트레일 조건

• 모든 정점이 짝수 차수를 갖는다면 아무 점에서나 시작해도 오일러 투어가 가능
• 만약, 홀수 차수를 갖는 정점이 2개이면 그 점이 시작점이나 끝점이 되면 역시 오일러 트레일을 그릴 수 있음

→ 쾨니히스베르크 다리의 그래프는 홀수 차수의 정점이 4개 이므로 오일러 트레일을 갖지 못함

4 같이 보기

• 그래프
• 한붓그리기

5 참고

• 위키백과 "그래프 이론"
• http://m.times.kaist.ac.kr/news/articleView.html?idxno=1526