Dado un grafo no dirigido y no ponderado de aristas.
'1#2', '2#3', '1#11', '3#11', '4#11', '4#5', '5#6', '5#7', '6#7', '4#12', '8#12', '9#12', '8#10', '9#10', '8#9'
donde por ejemplo el nodo 1 y el nodo 2 tienen una arista directa
ahora la pregunta es, qué algoritmo se puede utilizar para encontrar el máximo número de nodos que pueden ser visitados (a partir de cualquier nodo), visitando un nodo como máximo una vez y sin atravesar de nuevo por cualquier borde
Su problema es el Problema del camino más largo y se sabe que es NP-difícil.
Por lo tanto, no hay ningún algoritmo de tiempo polinómico conocido para responder a su problema, y a menos que P=NP no hay tal algoritmo.
Así que para responder a tu pregunta puedes enumerar todos los caminos posibles visitando como máximo una vez cada vértice y encontrar el más largo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
