Circuitos de Hamilton y Circuitos de Euler

Que tal...

Un circuito de Hamilton, es aquel que pasa por cada vertice solo una vez, y regresa a su lugar de partida. El programa que comparto solo puede hacerlo con grafos no-dirigidos.

Un circuito de Euler, es aquel que pasa por cada vertice, y regresa al vertice de partida. De la misma manera, solo es para grafos no dirigidos.

Explicacion de funcionamiento.

Tenemos la clase vertex, que representa un vertice en el grafo. Para cada las aristas de ese nodo o vertice, se tiene un arreglo que se llama edges, y solo contiene la letra de los vertices con los cuales esta conectado.

La clase Graph, representa un grafo, el cual contiene vertices. Estos son introducidos en un arreglos llamado @vertices. Esta clase solo se usa para contener a los vertices que ya tenemos.

En el archivo graphs_controller, se pueden llamar los metodos euler_circuit y hamilton_circuit.

Importante.Si quieres usar los dos metodos. Es decir, quieres el circuito hamiltoniano y Euleriano, primero tienes que invocar al hamiltoniano, y despues al euleriano. La razon de esto, es que para hacer el euleriano, desconecto todos los vertices. Entonces, si lo invocas al reves, no funcianara el de hamilton.

El codigo no esta nada documentado, pero lo dificil es saber como sacar el circuito. No tanto descifrar el codigo. Ruby es sencillo de leer.

Espero les sirva.

Link al Programa