목록CS/알고리즘&그래프 (1)
공부방
오일러 순환과 해밀턴 순환
그래프 그래프 G는 다음의 두 가지 집합으로 구성되며, G={V,E}로 표시된다. 여기서 V는 정점들의 집합이며, E는 정점들을 연결하는 선들의 집합이다. 차수 정점 u에 접합된 연결선의 수 차수는 deg(u)와 같이 표기하기도 함 오일러 경로를 갖기 위한 필요 충분 조건 2개 이상의 정점을 갖는 루프가 없는 연결 그래프에서 홀수 차수를 갖는 정점이 하나도 없거나 오직 두 개만 존재해야 한다. 특히 모든 정점이 짝수 차수를 가지면 오일러 순환이 존재하며, 이 그래프는 오일러 그래프이다. 해밀톤 경로(Hamitonian Path) 그래프 G에서 모든 정점을 정확히 한 번만 지나는 경로 해밀톤 순환(Hamiltonian cycle 혹은 circuit) 시작점과 끝점이 같은 해밀톤 경로 TSP 알고리즘 하나의..
CS/알고리즘&그래프
2023. 7. 12. 23:15