PENERAPAN MODIFIKASI ALGORITMA WARNSDORFF DALAM IDENTIFIKASI LINTASAN DAN SIRKUIT HAMILTON PADA GRAF SEDERHANA

Abstract

Graph Hamilton is one of the concepts in graph theory related to a path that visits each vertex exactly once before returning to the starting vertex in the case of a Hamiltonian circuit. This research focuses on determining whether a graph has a Hamiltonian path or circuit using the Warnsdorff algorithm. The Warnsdorff algorithm was originally developed to solve the Knight’s Tour problem on a chessboard by selecting the vertex with the smallest degree to reduce the likelihood of getting stuck without any further moves. However, this algorithm has a weakness as it does not always succeed in finding a Hamiltonian path in various types of graphs. Therefore, this study modifies the Warnsdorff algorithm by implementing a strategy of selecting the starting vertex based on the smallest degree and applying a re-search mechanism if a Hamiltonian path is not found. If the path is still not found, the starting vertex is replaced with the next smallest-degree vertex until a path is found or all possibilities have been tested. This modification is expected to increase the algorithm’s chances of finding a Hamiltonian path compared to the unmodified Warnsdorff algorithm. The research methodology includes applying the modified Warnsdorff algorithm to various simple graphs and analyzing its performance in finding Hamiltonian paths. The results show that the modified Warnsdorff algorithm can identify Hamiltonian paths in certain graph structures. This modification not only improves the success rate of finding Hamiltonian paths but also reduces the number of steps in some cases, with potential applications in route optimization and network design. The conclusion of this study confirms that although modifying the Warnsdorff algorithm improves its success in finding Hamiltonian paths, further development is still necessary to make it more reliable in handling graphs with more complex structures.