Primer problema que Adolfo Quirós, de la Real Sociedad Matemática Española, organismo que en 2011 cumple cien años, y profesor de la Universidad Autónoma de Madrid, plantea a los lectores de "El País". Cada semana, hasta completar las 30 que dura la promoción, plantean nuevos desafíos.
El dibujo es un grafo, y representa una serie de puntos, llamados vértices unidos por unos trazos llamados aristas. Un camino en el grafo es un recorrido por el grafo que usa las aristas para saltar de vértice en vértice.
Encuentra un camino en el grafo de forma que se recorran todos los números una única vez y se vuelva al número inicial, o bien, demuestra que es imposible.
Solución:
Antes de dar la solución, expliquemos unos conceptos previos:
Un grafo $$G$$ es un par $$G=(V,E)$$, donde $$V$$ es un conjunto finito (vértices, nodos) y $$E$$ es un multiconjunto de pares no ordenados de vértices, denotados por $$\left\{{x,y}\right\}$$, que se denominan lados, aristas, etc.
En este caso decimos que x e y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G.
Una sucesión alternada de vértices y lados u1, e1, u2, e2, . . . , ek, uk+1 tal que ei = [ui, ui+1] se denomina cadena en un grafo y camino en un digrafo.
En este caso decimos que x e y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G.
Una sucesión alternada de vértices y lados u1, e1, u2, e2, . . . , ek, uk+1 tal que ei = [ui, ui+1] se denomina cadena en un grafo y camino en un digrafo.
La cadena cerrada es un ciclo si todos los vértices (excepto los extremos) son distintos. El camino cerrado es un circuito si todos los vértices (excepto los extremos) son distintos.
Se dice que un grafo simple G = (V,E) es bipartito si el conjunto de vértices V (V1 ∪ V2 = V, V1 ∩ V2 = ∅ se puede dividir en dos conjuntos disjuntos V1, V2, de tal manera que toda arista e ∈ E conecta un vértice de V1 con un vértice de V2.
Un camino simple que contiene cada vértice de G se denomina camino Hamiltoniano de G; análogamente, un ciclo Hamiltoniano de G es un ciclo que contiene todos los vértices de G. Tales caminos y ciclos son asíllamados después que Hamilton (1856) describió, en una carta a su amigo Graves, un juego matemático sobre el dodecaedro en el cual una persona coloca cinco alfileres en cinco vértices consecutivos y a otra se le exige completar un camino simple hasta completar un ciclo.
Se dice que un grafo simple G = (V,E) es bipartito si el conjunto de vértices V (V1 ∪ V2 = V, V1 ∩ V2 = ∅ se puede dividir en dos conjuntos disjuntos V1, V2, de tal manera que toda arista e ∈ E conecta un vértice de V1 con un vértice de V2.
Un camino simple que contiene cada vértice de G se denomina camino Hamiltoniano de G; análogamente, un ciclo Hamiltoniano de G es un ciclo que contiene todos los vértices de G. Tales caminos y ciclos son asíllamados después que Hamilton (1856) describió, en una carta a su amigo Graves, un juego matemático sobre el dodecaedro en el cual una persona coloca cinco alfileres en cinco vértices consecutivos y a otra se le exige completar un camino simple hasta completar un ciclo.
Un grafo es hamiltoniano si contiene un ciclo Hamiltoniano. Este es el caso del primer grafo dibujado por el profesor Quirós, conocido como el Dodecaedro Hamiltoniano.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo.(No existe un método de resolución general).
Veamos ahora la Solución del problema planteado:
La forma más fácil de resolverlo es darse cuenta de que se trata de un grafo muy conocido, llamado Grafo de Herschel, el cuál se sabe que es bipartito y además tiene un número impar de vértices, por lo que no puede ser un grafo hamiltoniano.
Otro método para resolver el problema es usar la coloración de grafos.
La forma más fácil de resolverlo es darse cuenta de que se trata de un grafo muy conocido, llamado Grafo de Herschel, el cuál se sabe que es bipartito y además tiene un número impar de vértices, por lo que no puede ser un grafo hamiltoniano.
Otro método para resolver el problema es usar la coloración de grafos.
Coloreemos los vértices de dos colores, por ejemplo, rojo y azul, de forma que los vértices rojos sólo se comuniquen directamente con los azules y los azules con los rojos. Nos quedarán así seis vértices rojos y cinco azules. Pues bien, si empezamos por un vértice rojo nuestro última etapa será también de ese color, pero entonces no habrá comunicación con el punto de partida (no están enlazados los puntos del mismo color). Pero si empezamos con un vértice azul (sólo hay cinco) será peor, ya que quedaremos atascados mucho antes de completar el circuito. Por tanto, el grafo de Herschel no tiene ningún ciclo hamiltoniano.
Por último podríamos demostrarlo matemáticamente:
Sea G = (V,A) un grafo e I un conjunto independiente en V (si no hay en I dos vértices adyacentes).
El número de aristas incidentes en vértices del conjunto independiente será la suma de las valencias de sus vértices, ya que al contabilizar cada una de ellas no aparecen repetidas, ya que no existe ninguna que tenga ambos vértices en I. Entonces:
Supongamos ahora que G es Hamiltoniano y sea C un ciclo hamiltoniano.Vamos a demostrar que el número de aristas de A que no están en C es mayor o igual que:
A cada x ∈ I, al eliminar las aristas de C, le quedan δ(x) − 2 aristas y además estas aristas no son aristas incidentes en ningún otro vértice de I, por lo que el número de aristas de A que no están en C será:
Como consecuencia de lo anterior si
entonces G no es Hamiltoniano
El conjunto independiente I = {8, 3, 11, 2, 4} de la figura del problema verifica la desigualdad anterior, por lo que el grafo de Herschel no puede ser hamiltoniano.
SOLUCIÓN DE "EL PAÍS": Y la solución es... no hay solución
No hay comentarios:
Publicar un comentario