야심한 밤의 수학 한스푼

Question

밑에 어떤분이 올려주신 짤인데요

이거 되게 신기하죠

얘는 hamilton cycle이란거를 이용한건데요,

쉽게말하면 우리가 생각하는 한붓그리기에서 시작점과 끝점이 동일한 상태에요.

여러분 오일러 다리문제 아시죠? 1이라는 섬에서 시작했다고 쳐봅시다. 그러면 1이라는 섬에서 갈 수 있는 섬은 3, 8, 15, 24가 있겠죠. 3을 갔다고 치면 6, 13, 22 등등이 있을거구요. 이렇게 이동하다가 1로 돌아오는 경로를 찾는 것과 동일합니다.

일반적인 hamilton cycle조차도 존재하기위한 섬과 다리들의 필요충분조건이 없는것으로 알려져 있어요. 얘는 특수한 cycle이기 때문에 수와 존재성 사이에 필요충분조건이 있을수도 있을지도 모르지만 저는 능력이 안돼서 모르겠네요.

밑에 출처 가보시면 작성자분이 c로 경로를 찾는 프로그램을 코딩해 놓으셨어요. c 좀 아시는분은 보면 이해가 될거고, 결과적으로 32일때는 유일한 경로를 가지고 그거보다 작으면 경로가 없다고 나오네요.

이러한 그래프와 경로 등등을 다루는 분야는 바로 이산수학입니다. 이산수학에는 다른 분야도 많겠지만, 그래프, 정렬, 알고리즘, 오토마타 등과 많은 연관성을 갖고 있어요. 기회가 된다면 한번쯤 들어보시는거 추천합니다. 상당히 재밌어요

센츄상어 · Accepted Answer

images

수능깎는​노인 · Answer

아 저렇게 이웃해도 섬을 다 이으면 되는거구나

최근 게시글 · 더보기