그래프 그리기 재밌다. Python/인접 행렬 시각화

파이썬은 데이터 시각화 툴이 너무 잘 되어 있어서 재미있다.

마지막 그림은 해밀턴_경로 중 하나이다. 그리고만 끝내기 심심해서 모든 해밀턴 경로의 경우의 수를 찾아봤다. DFS를 조금 변형해서 현재 vertex의 방문 가능한 지점을 쌓아두고 꺼내 쓰면서 DFS를 복귀할 때 방문을 초기화하고 해밀턴 경로가 성립하는 경우를 세면서 찾을 수 있다. NP-완전 문제이기 때문에 그냥 이렇게 완전 탐색으로 찾아야 한다. 해밀턴 경로를 찾기 위한 조건은 아직 발견되지 않았다. 5X5 바둑판은 4324개의 해밀턴 경로가 있다. 5X5는 금방 찾는다. 7X7 바둑판은 10년 전 쯤 세는데 매스매티카에서 5시간 걸렸다는 듯 하다[1]. 내 라이젠 3600, C++ 구현에서 찾았을 때 몇 분 기다리다가 응답이 없어서 세는걸 그만 두었다.