[TIL][240801] Graph

새로 알게 된 점은 무엇인가?

Graph?

그래프란 수학에서, 좀 더 구체적으로 그래프 이론에서 그래프란 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조를 말한다.

 

놀랍게도 그래프는 18세기 유럽의 프레겔 강과 그 다리들을 가지고 했던 놀이에서 유래되었다. 프레겔 강은 2개의 큰 섬이 있었고 섬과 도시를 연결하는 7개의 다리가 있었다. 이 당시 사람들은 "7개의 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?" 라는 질문을 시작으로 많은 사람들이 풀이에 도전해봤지만 풀 수 있는 사람은 아무도 없었다.

 

오일러 경로

대학시절 공학수학 시간에 날 엄청나게 괴롭혔던 레온하르트 오일러가 이 문제에 대해서 조사, 논문을 작성하게 되는데, 이것이 그래프 이론의 시작이라고 한다.

 

각 다리를 a~g 지역을 A~D 라고 이름을 부여하고 그림1과 같이 도식화하였는데, 이는 그림2와 같이 A~D를 정점(Vertax), a~g를 간선(Edge)으로 구성된 그래프라는 수학적 구조로 볼 수 있다.

 

해밀턴 경로

오일러 경로는 간선을 기준으로 한다면, 해밀턴 경로는 정점을 기준으로 한다. 하지만 해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 문제다. (NP 문제 중 NP-난해인 문제를  NP-완전 문제라 부른다)

*NP 복잡도 다음에 정리하기

 

원래의 출발점으로 돌아오는 경로를 해밀턴 순환이라 부른다. 이 중 최단 거리를 찾는 문제는 알고리즘 분야에서 대표적인게 외판원 문제(TSP: Traveling Selasman Problem)이다. 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제, 즉 최단 거리인 해밀턴 순환을 찾는 문제이며 NP-난해 문제로 분류된다.

실제로 미국의 20개의 도시를 찍고 돌아오는 총 경로의 수는 20!(2,432,902,008,176,640,000)이다. 240경...

 

 

 

 

---

무엇을 느꼈고 내일은 무엇을 할까?

트리를 공부하면서 그래프에 대한 내용이 간혹 나올 때마다 '트리도 그래프의 일종이다.'라고 짧게 언급하고