Algoritmo De Fleury

Fleury algoritmo se utiliza para construir o identificar un ciclo euleriano en un gráfico euleriano.

La clase de los problemas que tienen los algoritmos no deterministas cuya etapa de reconocimiento puede ser realizado por un tamaño de entrada algoritmo polinomio se llama NP. Una pregunta sigue sin respuesta es qué se refiere a qué tipo de algoritmo es más eficiente, no-determinista o determinista. Una forma de probar que los algoritmos no deterministas son más eficientes que el determinista es demostrar que un problema NP no está en P. Nadie ha sido capaz todavía. Sin embargo, para demostrar que las dos clases son iguales (P = NP), entonces taremos para mostrar que para cada problema tiene una solución perteneciente a NP con un algoritmo de tiempo polinomial determinista. Tampoco se demostró (pocos creen en la veracidad de esta afirmación).

Definición: Un problema X se llama un problema NP-duro si todo NP es reducible polinómicamente X.

Definición: Un problema X se llama NP-completo si (1) X pertenece a NP, y (2) X es NP-Hard.

Cocine demostró que hay problemas NP-completos: en particular, expuso un cierto problema que se describe brevemente. Una vez que encuentre un problema NP-completo, probar que otros problemas también son NP-completo. Para que vamos a definir el siguiente lema.

Lema

Un problema es NP-Completo X, si (1) X pertenece a NP, y (2) Y es polinómicamente reducible a X, Y a cualquier problema, que es NP-completo.

Demostración: Por la condición 2 en la definición de NP-completo, todos los problemas de NP es Y. polinómicamente reducible Pero como Y es polinómicamente reducible reducible a X y es una relación transitiva, todos los problemas de NP es reducible a polinómicamente X. posesión esto y la condición 1, la evidencia es que X es NP-completo.

Algoritmo de Fleury

funcionar Fleury (G = (V, E): el gráfico): ruta

G ': G = {G' = (V ', E')} v0: = un vértice de G 'C: = [v0] {Inicialmente, el circuito contiene sólo v0} Aunque no está vacía

vi: = último vértice de C Si he visto sólo tiene una arista incidente;

ai: = la arista incidente vio en G '

Pero

ai: = una arista incidente vio en G 'y eso no es un puente

Retire el gráfico ai borde G 'Añadir interino al final de C vj: = vértice conectado a la sierra por ahí vj Añadir al final de C

Volver C

Figura: 4a, 4b y 4c

Para entender cómo Fleury algoritmo, considere la gráfica de la Figura 4a. Supongamos que el algoritmo comienza con el ápice 6. Él puede elegir uno de los bordes h, d, e o i. Suponiendo que lo

...