Timeline for Run Christofides algorithm by hand with wrong result
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2018 at 16:12 | vote | accept | Ryan Cameron | ||
| Nov 15, 2018 at 13:02 | comment | added | John L. | You can also check the example at Wikipedia. "That is not an Eulerian path as you visit a vertex more than once in that path". Eulerian path is about visiting each edge exactly once. You are talking about Hamiltonian path. | |
| Nov 15, 2018 at 12:00 | comment | added | John L. | "You have obtained a multigraph", a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. There are two edges between D and E. There are two edges between A and F. | |
| Nov 15, 2018 at 9:24 | comment | added | Ryan Cameron | Additionally, this is not true either: "let us select the Eulerian path A -> F -> A -> C -> B -> D -> E -> D -> A." - That is not an Eulerian path as you visit a vertex more than once in that path. | |
| Nov 15, 2018 at 9:22 | comment | added | Ryan Cameron | This is not true: "In the last picture, you have obtained a multigraph all of whose vertices have even degrees." - The vertices E, D, A, and F has an odd degree. | |
| Nov 14, 2018 at 13:11 | comment | added | John L. | 1. You can treat is as a TSP if you assume, for example, all missing direct distances between cities are sufficient large or simply infinity. In that way, those missing distances will not affect the solution. However, it is not a metric space still. 2. To obey the triangle inequality, you can just add 10 to each distance you have specified and let the all the missing distances be 20. | |
| Nov 14, 2018 at 12:42 | vote | accept | Ryan Cameron | ||
| Nov 15, 2018 at 9:28 | |||||
| Nov 14, 2018 at 12:40 | comment | added | Ryan Cameron | I am new to this, so thank you for the side notes! I got some questions: 1. Does each vertex have to be connected to each other vertex for it to be a valid TSP? I mean it is still possible to create a "TSP" route even with that route missing, so I would say it is valid - but I have been wrong before. 2. Do you think (or know) if it is possible to increase the weights of some of the vertices in my graph in such a way, so that it obey the triangle inequality? I think more messy looking graphs are better at representing real world map scenarios, that's why I created it as it is. | |
| Nov 13, 2018 at 23:26 | history | edited | John L. | CC BY-SA 4.0 |
Is this problem appropriate for Christofides algorithm?
|
| Nov 13, 2018 at 23:04 | history | answered | John L. | CC BY-SA 4.0 |
