Determinazione del circuito più lungo in un grafo

[Ishima1]

Buonasera,mi è sorto un dubbio. È possibile ricavare il circuito più lungo all'interno di un grafo attraverso l'utilizzo di semplici calcoli? Nel caso in cui sia euleriano, è semplice,ma negli altri casi?
Grazie in anticipo!

[andreaciceri96]

Ignoro la matematica dei grafi e le mie conoscenze si fermano a considerarli solo come strutture informatiche ma la tua domanda mi ha incuriosito. Tempo fa mi ero ritrovato a dover implementare il famoso algoritmo di Dijkstra per determinare il percorso piu' corto per un mio progetto personale e non avevo mai pensato al problema opposto.
Wikipedia dice che e' NP-hard: https://en.wikipedia.org/wiki/Longest_path_problem

[axpgn]

Pare che un olandese, tale Jos Wemmnacker abbia trovato una soluzione "pratica e veloce" ...

Riporto la notizia in originale:

"He creates an analog model of the graph by knotting together pieces of string in exact scale (or connecting the pieces of string to small rings).
The result is obtained by two simple operations.
Pick up the string structure at any node (point) and let it hang freely.
Pick up again at the lowest node and hang it again, and you have the longest path.
As simple as that!"

Prova!

Cordialmente, Alex

[andreaciceri96]

Questa soluzione e' geniale
Ora basta programmare un motore fisico...