Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2409.11563 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916399153152000 |
|---|---|
| author | Kurapov, Sergey Davidovsky, Maxim Polyuga, Svetlana |
| author_facet | Kurapov, Sergey Davidovsky, Maxim Polyuga, Svetlana |
| contents | The monography considers the problem of constructing a Hamiltonian cycle in a complete graph. A rule for constructing a Hamiltonian cycle based on isometric cycles of a graph is established. An algorithm for constructing a Hamiltonian cycle based on ring summation of isometric cycles of a graph is presented. Based on the matrix of distances between vertices, the weight of each cycle is determined as an additive sum of the weights of its edges. To construct an optimal route of a graph, the basic idea of finding an optimal route between four vertices is used. Further successive constructions are aimed at joining an adjacent isometric cycle with an increase in the number of vertices by one unit. The recursive process continues until all vertices of the graph are connected. Based on the introduced mathematical apparatus, the monography presents a new algorithm for solving the symmetric Traveling salesman problem. Some examples of solving the problem are provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11563 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithmic methods of finite discrete structures. Hamiltonian cycle of a complete graph and the Traveling salesman problem Kurapov, Sergey Davidovsky, Maxim Polyuga, Svetlana Combinatorics Discrete Mathematics The monography considers the problem of constructing a Hamiltonian cycle in a complete graph. A rule for constructing a Hamiltonian cycle based on isometric cycles of a graph is established. An algorithm for constructing a Hamiltonian cycle based on ring summation of isometric cycles of a graph is presented. Based on the matrix of distances between vertices, the weight of each cycle is determined as an additive sum of the weights of its edges. To construct an optimal route of a graph, the basic idea of finding an optimal route between four vertices is used. Further successive constructions are aimed at joining an adjacent isometric cycle with an increase in the number of vertices by one unit. The recursive process continues until all vertices of the graph are connected. Based on the introduced mathematical apparatus, the monography presents a new algorithm for solving the symmetric Traveling salesman problem. Some examples of solving the problem are provided. |
| title | Algorithmic methods of finite discrete structures. Hamiltonian cycle of a complete graph and the Traveling salesman problem |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.11563 |