Circuito de Hamilton y Euler

CIRCUITOS DE HAMILTON
W.R. Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.
Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasandoexactamente una vez por cada vértice. 
Un circuito hamiltoniano como un paseo circuito que pasa a través de cada un de los vértices exactamente una vez.
Ejemplo:
Encuentre un circuito de Hamilton en el siguiente grafo:


El siguiente es un resultado general sobre la existencia de paseos o circuitos hamiltonianos.

Sea G un grafo no dirigido de tipo lineal de n vértices. Si la suma de losgrados para cada par de vértices de G es n - 1 o mayor, entonces existe un paseo de Hamilton en G.

Ejemplo:

La consideración anterior es una condición suficiente pero no necesaria para la existencia de un paseo hamiltoniano en un grafo.
Ejemplos:
¿Cuál de los grafos siguientes admite un ciclo hamiltoniano?

Solución
(a) No admite ciclos hamiltonianos. El razonamiento es el siguiente: Sise empieza en v1, v2, v3, v4 y si se está en los demás vértices, en el v5  se  estará  dos veces.
Si se empieza en v5, para luego ir a los vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por v5 (puesto que se empezará en v5). Para completar el ciclo, se debe regresar a v5, por lo que se pasa tres veces por él.
W.R. Hamilton (1805-1865) inventó (y patentó) un juego enel que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

CIRCUITO DE EULER
Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano.
Un circuito euleriano es una trayectoria que empieza ytermina en el mismo vértice
y recorre cada arista exactamente una vez.
Ejemplos:

(a) No lo admite porque v4 es un vértice aislado.
(b) No lo admite porque cualquier ciclo utilizará la arista e1 dos veces.
(c) El circuito v1 – v2 – v1 es euleriano.
(d) El circuito v3 – v1 – v2 – v3 es euleriano.
(e) No admite ningún circuito euleriano.
(f)  v1 – v2 – v3 – v4 – v2 – v5 – v1 es un circuitoeuleriano.
Existe un criterio preciso para saber cuando un grafo admite un circuito euleriano.
Este criterio lo proporciona el siguiente teorema.
Teorema. Sea G un grafo. G contiene un circuito euleriano sí y sólo sí:
• G es conexo.
• Cada vértice de G es de grado par.

Ejemplo:
Verificar si los siguientes grafos no dirigidos tienen un paseo o circuito de Euler.

Paseo de Euler
SI
Si
SiCircuito de Euler
No
Si
No
 

Paseo de Euler
Si
Si
Circuito de Euler
No
Si
 

RAZONAMIENTO DEDUCTIVO

El razonamiento deductivo, también llamado demostración o prueba, es el razonar a partir de hechos demostrados, utilizando pasos lógicamente válidos para llegar a una conclusión. Una demostración puede servir varios propósitos. Los matemáticos a menudo utilizan lademostración para verificar que una conjetura es verdadera para todos los casos, no sólo para aquellos examinados, o para convencer a otros. Las demostraciones a menudo ayudan a responder a la pregunta: ¿Por qué?
El uso de la demostración para explicar el por qué, es una extensión natural para los estudiantes en este punto del curso y les ayuda a profundizar su comprensión. Este capítulo resalta estepropósito iluminador de la demostración o prueba.

Ejemplo
Problema
Terry hace lo siguiente para factorizar la expresión 3x3 + 6x2 + 3x.
 
• Primero factoriza 3x usando la Propiedad Distributiva:
3x3 + 6x2 + 3x = 3x(x2 + 2x + 1)
 
• Luego reconoce que el segundo factor está en la forma de
a2 + 2ab + b2, y recuerda que a2 + 2ab + b2 = (a + b)2
 
• Finalmente, reescribe el segundo factor...