ALGORITMO DE FLEURY

1. elegir cualquiera de los vértices para empezar
2. desde ese vértice tomar una ventaja de atravesar (ver más abajo para regla importante)
3. oscurecer esa ventaja, como un recordatorio de que no se puede atravesar otra vez
4. viaje que el borde, llegando a la siguiente vértice
5. repita 2-4 hasta que todos los bordes se han atravesado, y que están de vuelta en el vértice de partida
en cada etapa del algoritmo:

• el gráfico original menos los bordes oscuros (ya utilizada) = grafo reducido
• una regla importante: nunca cruzar un puente de la gráfica reducida a menos que haya otra opción
• ¿por qué debemos respetar esa regla?

Notas:

• el mismo algoritmo que trabaja para los caminos de Euler
• antes de comenzar, use los teoremas de Euler para comprobar que la gráfica tiene un camino de Euler y / o circuito de encontrar!
• cuando se hace esto en el papel, usted puede borrar de cada borde a medida que lo atraviesan
• esto hará que el grafo reducido visible y evidente de sus puentes

Ejemplo

Paso de la receta	Gráfica marcada	Grafo reducido
Elige cualquiera de los vértices (F, por ejemplo)
Viaje de F a C (Elección arbitraria)
Viaje de C a D (Arbitrario)
Los viajes de D a A (Arbitrario)
Viajar de A a C (No se puede ir a la B: esa ventaja es un puente del grafo reducido, y hay otras dos opciones, elegimos uno de ellos)

El resto del viaje es obvia, y es el circuito completo de Euler:
(F, C, D, A, C, E, A, B, D, F)

ALGORITMOS GENETICOS

Algoritmos Genéticos (AGs) son algoritmo adaptativo de búsqueda heurística basa en las ideas evolucionistas de la selección natural y genética. El concepto básico de gas está diseñado para simular los procesos en los sistemas naturales necesarios para la evolución, específicamente los que siguen los principios básicos establecidos por Charles Darwin de la supervivencia del más apto. Como tales, representan una explotación inteligente de una búsqueda al azar dentro de un espacio de búsqueda definido para resolver un problema.
En primer lugar por primera vez por John Holland en los años 60, algoritmos genéticos ha sido ampliamente estudiado, experimentado y aplicado en muchos campos en los mundos de la ingeniería. No sólo el gas proporcionan una alternativa a los métodos de resolución de problemas, que siempre supera a otros métodos tradicionales en la mayoría de los problemas de enlace. Muchos de los problemas del mundo real consistía en encontrar los parámetros óptimos, lo que podría resultar difícil para los métodos tradicionales, pero ideal para el gas. Sin embargo, debido a su destacado desempeño en optimización de gas han sido erróneamente considerada como método para mejorar la función. De hecho, hay muchas maneras de ver los algoritmos genéticos. Tal vez lo más usuarios llegan a Gas en busca de un solucionador de problemas, pero esto es una visión restrictiva [De Jong, 1993].
Aquí, vamos a examinar de gas como una serie de cosas diferentes:

GAs como solucionadores de problemas

GA como un puzzle difícil técnica

De gas como base para el aprendizaje de máquinas competente

Gas como modelo computacional de la innovación y la creatividad

Gas como modelo computacional de sistemas innovadores otros

Gas como filosofía rectora

Sin embargo, debido a diversas limitaciones, sólo estaríamos hablando de GAs como solucionadores de pro blema y la máquina competentes aprendiendo aquí. También se examinará cómo el gas se aplica a los campos completamente diferentes.
Muchos científicos han tratado de crear programas de vida. Estos programas no se limitan a simular la vida, sino tratar de mostrar el comportamiento y las características de un organismos reales, en un intento de existir como una forma de vida. Se han hecho sugerencias de que la vida artificial con el tiempo se convertiría en la vida real. Tal sugerencia puede sonar absurdo en este momento, pero ciertamente no inverosímil, si la tecnología sigue avanzando al ritmo actual. Por lo tanto, vale la pena, en nuestra opinión, teniendo un párrafo a cabo para discutir cómo Alife está conectado con el gas y ver si esa predicción es descabellada y sin fundamento.

PROBLEMA DE LAS 8 REINAS (AJEDREZ)

Dando color a los gráficos de la reina

El n×n reina gráfico tiene los cuadrados de n×n tablero de ajedrez de sus vértices y dos vértices son adyacentes si y sólo si, las reinas puestos en las dos plazas se atacan mutuamente.

La prueba es sencilla: Cuando el tablero de ajedrez es considerado como el cuadrado cartesiano de {0,1,...,n-1} , color de vértice (i,j) por el (j-2i) mod n . Esta construcción se ilustra a continuación el n=5 y n=7 . 

0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1

0 1 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0 6 0 1 2 3 4 5 4 5 6 0 1 2 3 2 3 4 5 6 0 1

Verificar que (siempre que n mod 6 es 1 o 5 ) que no hay dos vértices del mismo color son adyacentes es un ejercicio de rutina, pero aquí están los detalles de todos modos.

Considere la posibilidad de vértices (i,j) y (x,y) del mismo color. Por definición,

(*) 2(xi) es congruente con (yj) mod n .

Si los dos vértices están en la misma fila (x=i) , entonces (*) implica y=j . Si los dos vértices están en la misma columna (y=j) , entonces (*) implica x=i desde n es impar. Si los dos vértices están en la misma diagonal, entonces xi=yj o xi=jy , en el primer caso, (*) implica (x,y)=(i,j) , en este último caso, (*) implica (x,y)=(i,j) desde el 3 no divide n .

El mismo argumento (con el "xi=yj o xi=jy" reemplazado por xi es congruente con yj mod n o xi es congruente con jy mod n), muestra que el color funciona incluso a las reinas mas poderosas, que se mueven en diagonal envolviendo el contorno del tablero de ajedrez. 

HAVEL-HAKIMI

es interesante saber cueando una lsita de enteros es o no grafica, o dicho en otras palabras es o no la lista de grados de un cierto grafo. Havel y Hakimi resolvieron esta cuestion a manera independiente en los años 1955 y 1962: una lista de enteros D1>=D2>=...>=Dv>=0 es grafica sii asimismo lo es la lista (presumiblemente no ordenada)

D2-1,D3-1....Dd1+1-1,Dd1+2,Dd1+3...,Dv

que se obtiene aleliminar D1 y restar una unidad a los D1 siguientes valores comprendidos entre D2 y Dd1+1.

en otras palabras si una lsita de enteros no negativosD1>=D2>=...>=Dv>=0 es grafica, siempre existe un grafo G(V,A) de vertices V={x1,...,xv} de manera que d(x1)=d1 y x1 es adyacente a los d1 vertices que le siguen. y reciprocamente, esta propiedad caracteriza completamente las listas que son grafixas.

asi pues, se puede diseñar un algoritmo sencillo , de complejidad lineal en el numero de vertices, que devuelve como salida si la lista de enteros es o no grafica: y que, en caso afirmativo, provee adicionalmente un metodo para construir un grafo cuya lista de grados coincide con la lista grafica de entrada.

ALGORITMO DE HAVEL-HAKIMI

ENTRADA:lista l=(d1,...,dn) con D1>=...>=Dv>=0.

P1   k=1

P2   mientras la lista k=(k1,..,kn) tengan entradas positivas hacer

P3   eliminar de k la primera entrada, k1

P4   restar una unidad a las primeras k1 entradas de la lita resultante

P5  k= reordenar la nueva lista asi obtenida en orden decreciente

P6  fin mientras

SALIDA: si la lista es nula entonces la lista inicial es grafica, en otro caso no lo es.

En verdad, los pasos P3 y P4 del algoritmo anterior consisten en pasar de la lista k=(K1,...,kn) a la lista   k(k2-1,...,kk1+1-1,k1+2,...,kn).

Caso de que el algoritmo devuelva una respuesta afirmativa, desandando el proceso que se ha descrito se puede construir sin dificultad un grafo cuya lista de grados es la lista inicial. Así, en este proceso de reconstruccion, cada entrada k1 suprimida en la lista se traduce en la aparicion de un nuevo vertice, adyacente a los k1 vertices cuyas valencias corresponden a las que han sido sustraidas tras la eliminacion de k1.

en conclusion, la lista de entrada es la grafica. para encontrar la realizacion de un grafo que tenga por lista de grados la lista de entrada andamos hacia atras el procediemiento seguido en el algoritmo. Como quiera que el proceso incluye reodernaciones de las valencias (y por tanto de los vertices).