Encontrar el camino más largo en un gráfico es problema irresoluble. Th decisión versión es $NP$-completa. Sin embargo, Dado el gráfico, existe un algoritmo eficiente para determinar la paridad del camino más largo en un gráfico?
El algoritmo debe de salida de SÍ, si la longitud del camino más largo es incluso lo contrario, el resultado es NO. También, ¿Cuál es la complejidad si queremos restringir la entrada a cúbicos gráficos?
Me parece que hay una fácil reducción del problema del camino hamiltoniano: Dar un grafo G se desea determinar si contiene un camino hamiltoniano o no, simplemente agregue un distinto camino de longitud igual a la longitud de la espera de hamilton camino menos 1. Ahora verificación de la paridad y ver si es igual a la de la ruta que hayas agregado o no.
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.
