¿Conocía Sherlock Holmes la teoría de grafos?

Junio de 2007, Número 10, páginas 37-51 ISSN: 1815-0640 ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello Resumen En este artículo se muestran las ventajas que ofrece la Teoría de Grafos a la hora de resolver determinados problemas clásicos de Matemáticas, que normalmente se suelen intentar probando una a una las diferentes posibilidades existentes, o bien por el conocido método de la “cuenta de la vieja”. Su principal objetivo es mostrar cómo esta Teoría facilita una gran cantidad de estrategias útiles para la resolución de estos problemas, de manera más rápida, elegante y sencilla de la habitual. Uno de estos problemas trata precisamente de cómo Sherlock Holmes pudo resolver un caso de asesinato, utilizando los grafos. Abstract In this paper, we show the advantages offered by Graph Theory to solve some classic mathematical problems, which are normally solved by using other non systematic techniques, such that to go one to one testing different possibilities or to use what in Spain is called “la cuenta de la vieja”. Its main goal is to show how Graph Theory allows to systematize and formalize a lot of useful strategies to find the solution of those problems in an easier, smarter and faster way than usual. One of these problems deals with the solution given by Sherlock Holmes to a case of murder by using graphs. Introducción Creemos que no es aventurado afirmar que, prácticamente, todos los que nos dedicamos actualmente a la enseñanza de las Matemáticas en cualquiera de sus niveles hemos tenido la experiencia de asistir cuando éramos alumnos a clases de esta disciplina en las que nuestro Profesor, con mayor o menor intención didáctica por su parte algunas veces, o simplemente para pasar el rato en las más de las ocasiones, nos planteaba una serie de problemas totalmente diferentes de los que estábamos habituados a resolver en el aula, a los que no siempre el más listo o empollón de la clase conseguía dar con su solución. Estos problemas, como los que trataremos en este artículo, eran denominados por el profesor problemas de ingenio, o problemas de razonamiento, o pasatiempos, o simplemente, problemas curiosos, y ciertamente que atraían la curiosidad de los más de los alumnos, que nos dedicábamos de lleno a intentar resolverlos, utilizando para ello todo tipo de razonamientos o estrategias particulares de cada uno que, extrañamente, no nos habían sido comentadas en clase y que cuando el primer afortunado en encontrar la solución de alguno de ellos la exponía al resto de sus compañeros, a petición del profesor, naturalmente, y con la lógica timidez, aunque ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 38 también con el orgullo personal que ello conllevaba, comentaba que su principal argumentación era que había utilizado la cuenta de la vieja para resolverlo. Sin embargo, esto que decimos, que podemos narrar como una experiencia propia, y por tanto, bastante moderna, fue precisamente lo que también le sucedió al genial matemático suizo Leonhard Euler (1707-1783), cuando en 1735 un grupo de jóvenes de la por aquel entonces ciudad prusiana de Königsberg fue a visitarle para pedirle que resolviera una cuestión que inquietaba sobremanera a los habitantes de la misma y sobre la que no llegaban a ponerse de acuerdo: saber si era posible encontrar un camino que atravesase las cuatro zonas de la ciudad en las que ésta quedaba dividida como consecuencia del paso del Río Pregel por la misma, pasando una y sólo una vez por cada uno de los siete puentes que existían para cruzarlo (véase la figura de abajo, que muestra un plano de la ciudad de Königsberg en tiempos de Euler, en la que los siete puentes aparecen coloreados de rojo y el Río Pregel de azul). Cuando esta cuestión, conocida actualmente con el nombre de Problema de los Puentes de Königsberg, le fue formulada a Euler, él mismo comentó: “Se me ha informado que, mientras unos dudaban la posibilidad de hacerlo y otros lo negaban, nadie sostenía que fuese posible realmente. El problema podría resolverse haciendo cuidadosamente una tabla de todos los recorridos posibles, asegurándose así, por inspección, de cuál de todos ellos, si es que alguno hay, satisface lo requerido. Este método de solución, sin embargo, es demasiado tedioso y difícil a causa del gran número de combinaciones posibles… Por tanto, lo descarté y traté de buscar otro que mostrase solamente si se puede descubrir un camino que satisfaga la condición prescrita” por lo que, como se puede apreciar, el propio Euler trató de resolver el problema de una forma algo más precisa y metódica que por la simple experimentación de todos los casos posibles. Para ello, Euler pasó primeramente a modelizar la situación, prescindiendo de la naturaleza física del problema y sustituyendo las cuatro zonas habitadas de la ciudad por puntos y los siete puentes por líneas entre esos puntos, con lo cual creó un diagrama geométrico, que constituyó el germen de lo que ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 39 actualmente conocemos como un grafo. De hecho, esta resolución del problema por Euler, que dio además una solución general al problema, independientemente del número de zonas o de puentes que hubiese en la ciudad, supuso el nacimiento de una nueva rama de las Matemáticas, la Teoría de Grafos, distinta de las tradicionales conocidas hasta el momento. Ésta es la razón por la que a Euler se le suele denominar el “padre de la Teoría de Grafos”, si bien es preciso constatar, en honor a la verdad, que actualmente se admite que esta teoría tiene también otros precursores distintos a Euler, como pueden ser Kirchhoff (problemas de redes eléctricas), Guthrie (problema de los cuatro colores) o Cayley (teoría de árboles). Una visión más completa del problema de los puentes de Königsberg puede ser consultada en Alfonso y otros (2004). Siguiendo entonces por nuestra parte la metodología de Euler, vamos a resolver en este artículo algunos de aquellos pasatiempos o problemas de ingenio, de los comentados anteriormente, empleando únicamente la Teoría de Grafos como herramienta para su resolución. El principal objetivo de este artículo es, por tanto, hacerle ver al lector que la Teoría de Grafos permite sistematizar y formalizar una gran cantidad de estrategias válidas para la resolución de estos tipos de problemas, que habitualmente suele encontrar el lector resueltos por otros métodos. No obstante, es también conveniente indicar que, a pesar de su sencillez y de la sin duda, potencial ayuda que esta teoría puede ofrecer como herramienta a utilizar a la hora de resolver ese tipo de problemas antes comentado, el estudio de esta teoría no está contemplado formalmente en ninguna de las etapas del Plan de Estudios español: ni en la Enseñanza Secundaria Obligatoria (12 a 16 años), ni por supuesto en la etapa anterior de Primaria (6 a 12 años), ni siquiera en las Facultades Universitarias de Matemáticas, en las que esta teoría no aparece como asignatura en muchas de ellas, o si aparece, lo hace en forma de asignatura optativa o de Libre Configuración, en el 2º Ciclo (a partir del tercer año de la licenciatura), o bien, como curso, también optativo por regla general, en los estudios de Máster o de Doctorado. La estructura de este artículo es la siguiente: en primer lugar se recuerdan en una primera sección los aspectos más básicos y elementales de esta teoría, que serán los que se utilicen en las citadas resoluciones, a las que va dedicada íntegramente la segunda sección. Para una visión más global y completa de la Teoría de Grafos, puede consultarse Harary (1991) o Bollobás (1979), por ejemplo. Aspectos básicos de la Teoría de Grafos Un grafo es un par G = (V, A), donde V es un conjunto numerable (no vacío) y A es un conjunto de pares no ordenados de elementos de V (eventualmente vacío). Los elementos de V se denominan vértices (o puntos o nodos) y los de A se denominan aristas (o líneas). Un grafo se dice etiquetado si en él se distinguen sus vértices, es decir, si se ha asignado un cierto nombre a cada uno de sus vértices. En caso contrario, el grafo se dice no etiquetado. Un ejemplo de grafo sería: G = (V, A), tal que V = {a, b, c, d}, A = {ab, ac, ad}. ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 40 En lo que sigue, denotaremos por G al grafo, por V = V(G) al conjunto de sus vértices y por A = A(G) al conjunto de sus aristas. Un grafo se puede representar de varias formas. De ellas, las más frecuente e intuitiva, aunque no operativa para el uso del ordenador, es mediante un diagrama en el que aparezca un punto por cada vértice y una línea entre cada dos vértices unidos. Así por ejemplo, el grafo anterior puede venir representado según: Figura 1 Para el propósito de lo que sigue, exigiremos que en un grafo no existan ni aristas repetidas (en cuyo caso se hablaría de multigrafos) ni lazos (aristas del tipo aa, en cuyo caso se hablaría de seudografos). No obstante, si se considera A como un conjunto de pares ordenados, es decir, si se les ha dado un cierto sentido a todas las aristas de un grafo, puede hablarse entonces de grafos dirigidos o digrafos. Dos vértices de un grafo se dicen adyacentes si ambos definen una arista en el grafo. En este caso, dichos vértices se dicen extremos de la arista. Una arista se dice que es incidente con cada uno de sus vértices extremos y dos aristas que comparten un extremo se dicen incidentes. En el grafo de la Figura 1 puede verse que los vértices a y d son adyacentes, pero b y c no lo son. Por otra parte, todas las aristas de dicho grafo son incidentes (en el vértice a). Se denomina grado de un vértice v de V(G) y se representa por d(v) o bien al número de aristas del grafo que son incidentes con él o bien al número de vértices del grafo que son adyacentes con él. Por convenio, un vértice no se considera adyacente consigo mismo. Los vértices de grado 0 se denominan aislados y los de grado 1, hojas o finales. Nótese que d(a) = 3, y d(c) = 1, en la Figura 1. Un grafo se denomina regular si todos sus vértices tienen el mismo grado. Si este grado es 2, el grafo se denomina ciclo (los ciclos se representan por Cn, siendo n el número de vértices del grafo). Se denomina grafo completo (y se representa por Kn) a todo grafo regular de n vértices y grado n-1 cada uno de ellos, es decir, al grafo que tiene todas las aristas posibles. En la Figura 2 aparecen representados C4 y K5, respectivamente, de izquierda a derecha. ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 41 Figura 2 Un grafo G se dice bipartito si su conjunto de vértices V se puede descomponer en dos subconjuntos disjuntos no vacíos V1 y V2 de modo que toda arista de G tenga un extremo en V1 y el otro en V2. Si el grafo bipartito tiene todas las aristas posibles, se denomina grafo bipartito completo. Si los cardinales de V1 y de V2 son m y n, respectivamente, entonces el grafo bipartito completo se representa por Km,n. Sea G = (V, A) un grafo. Un grafo G' = (V', A') se dice subgrafo de G si V' está contenido o es igual que V y A' está contenido o es igual que A. De entre los posibles subgrafos de un grafo, tienen especial trascendencia los subgrafos maximales o spanning. Un subgrafo G' = (V', A') de un grafo G = (V, A) se denomina maximal o spanning si V = V', es decir, si G' tiene los mismos vértices que G. Sea G = (V, A) un grafo. Se denomina grafo complementario de G al grafo que tiene el mismo conjunto de vértices que G y verifica que entre cada dos de esos vértices existe una arista si y sólo si dicha arista no existe en G. Nótese que el grafo complementario de un grafo no es un subgrafo de dicho grafo. Sea v un vértice del grafo G. Se denota por G-v al subgrafo de G que se obtiene eliminando el vértice v y todas las aristas incidentes con él (aunque el otro extremo de tales aristas permanezca). Sea G = (V, A) un grafo. Un camino en G es una sucesión finita de vértices y aristas alternados, cuyo primer elemento es un vértice, tal que dos elementos consecutivos de la misma sean siempre incidentes. Un camino en el que todas sus aristas sean distintas se denomina recorrido. Un arco en G es un recorrido en el que todos los vértices que lo forman son distintos, y finalmente, un ciclo en G es un camino cerrado en G que es un arco excepto en el hecho de que el primer y último vértice coinciden. En el grafo de la Figura 3, la sucesión de vértices (se omiten las correspondientes aristas) a,c,d,g,d,b, sería solamente un camino, mientras que los vértices a,c,d,g,h,e,b ya formarían un arco. Por otra parte, d,e,h,g,d sería un ciclo. ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 42 Figura 3 Un camino en un grafo se dice euleriano si en él entran todas las aristas y además una sola vez cada una de ellas (puede ser abierto o cerrado), mientras que se dice hamiltoniano si en él entran todos los vértices y además una sola vez cada uno de ellos. Nótese que en el grafo de la Figura 3 no hay caminos eulerianos (en Teoría de Grafos se prueba que para que existiesen, el número de vértices de grado impar debería ser 0 (y entonces el camino sería cerrado: empezaría y terminaría en el mismo vértice) ó 2 (camino abierto: empezaría en un vértice y terminaría en otro distinto)). Sin embargo, en el grafo de la figura hay 4 vértices de grado impar. Un grafo se dice conexo si dos cualesquiera de sus vértices pueden unirse mediante un arco. Si un grafo no es conexo, se dice disconexo. El grafo de Fig. 3 es claramente conexo. Algunos Problemas resueltos por Teoría de Grafos Se presentan en esta sección una serie de problemas clásicos, del tipo de los comentados en la introducción, que pueden ser resueltos utilizando la teoría de grafos. Muchos de ellos son problemas ya conocidos y suelen aparecer en otros textos resueltos por otros métodos. En todos ellos vamos a comprobar que la teoría de grafos nos ayuda a resolverlos de forma más sencilla. Problema 1.- Vecinos incompatibles. Se desea sentar a 8 personas en los vértices de una mesa octogonal, pero prestando atención a la siguiente condición: cada uno de ellos no acepta sentarse junto a algunos de los demás. Deducir si es posible hacerlo, respetando que A no quiere sentarse junto a B ni D; B no quiere sentarse junto a A, E, F ni H; C no quiere sentarse junto a D ni E; D no quiere sentarse junto a A, C ni G; E no quiere sentarse junto a B, C ni F; F no quiere sentarse junto a B, E ni H; G no quiere sentarse junto a D ni H; y, por último, H no quiere sentarse junto a B, F ni G. ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 43 Normalmente, este problema se intenta resolver probando una a una las posibilidades que a cada uno se le ocurran, sin orden ni concierto, es decir, sin emplear ni una estrategia ni un procedimiento sistemático de actuación. Por otra parte, dado que el número total de posibilidades que hay para sentar a las 8 personas en una mesa octogonal es 5040 ( (8-1)! = 7!), sería un esfuerzo bastante improductivo intentar escribirlas todas e ir eliminando una a una aquéllas que no satisficiesen las condiciones exigidas. Sin embargo, veremos que la Teoría de Grafos nos ofrece una forma de resolver el problema muy corta, sencilla y elegante. Para ello, construiremos un grafo asociado al enunciado de tal forma que cada persona será un vértice y dos vértices compartirán arista en caso de que sus representantes no acepten sentarse juntos (grafo de la izquierda de la figura). Basta tomar entonces el grafo complementario del anterior, en el que las aristas representarán ahora las posibles compatibilidades. Es muy fácil encontrar entonces en este último grafo un 8-ciclo que nos proporciona la solución. Una posible configuración de la mesa sería la siguiente: [ B, C, H, A, F, G, E, D ]. Problema 2.- Personas que se conocen. Dada una reunión de personas, probar que siempre habrá dos de ellas que conozcan al mismo número de personas. Nótese que un enunciado equivalente al anterior, pero usando terminología de grafos, sería el siguiente: dado un grafo cualquiera, de n vértices, probar que al menos dos de ellos tienen el mismo grado. Ahora es muy sencillo de resolver. Supongamos que no existe tal grafo. Como el grado máximo de cada vértice será (n-1), al no poder ser un vértice adyacente consigo mismo, y el grado mínimo será 0, en caso de que ser aislado, el número de valores distintos que pueden tomar los grados de los vértices es exactamente n. Entonces, al haber también n vértices, la única posibilidad de que no haya vértices ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 44 con el mismo grado es que un vértice tenga grado 0, otro 1, otro 2, y así sucesivamente hasta otro que tenga grado (n-1). Sin embargo, aquí se observa una contradicción, pues si hay un vértice de grado 0, esto significa que dicho vértice es aislado, por lo que ningún otro vértice podrá ser adyacente con él. O lo que es lo mismo, ningún vértice podrá tener grado (n-1), como habíamos supuesto. Por tanto, al menos dos vértices tendrán el mismo grado, o volviendo al enunciado original, siempre habrá dos personas (puede haber más, lógicamente) que conozcan al mismo número de otras personas. Problema 3.- Seis personas. Probar que en toda reunión de seis personas, siempre habrá tres que se conozcan, o bien tres que no se conozcan entre sí. Probar también que esto no ocurre siempre en grupos de cinco personas. Para resolver este problema traducimos de nuevo su enunciado a Teoría de Grafos (de hecho, este problema es conocido en esa teoría con el nombre de “Problema de Ramsey”). La cuestión es, si dado un grafo cualquiera de seis vértices, será siempre posible encontrar un triángulo en él (un C3) o en su complementario. Sea entonces A un vértice cualquiera del grafo, que fijaremos a partir de ahora. Supongamos que A es adyacente con al menos tres vértices distintos, que podemos decir, sin pérdida de generalidad, que son B, C y D. Entonces, si existe una arista entre dos cualesquiera de dichos vértices, habríamos acabado tomando el triángulo formado entre A y dichos dos vértices. En caso contrario, entonces B, C y D no compartirán arista alguna, por lo que en el grafo complementario formarán forzosamente un triángulo. Por otro lado, si A no fuese adyacente con al menos tres vértices, tomaríamos el grafo complementario. Al haber cinco vértices más, y dado que al menos tres de ellos no eran adyacentes a A en el grafo original, es seguro que A será adyacente a al menos tres vértices en éste. Podemos proceder de manera análoga, con lo que queda probado el problema en todo caso. Es inmediato demostrar que esto no se cumple en general para cinco vértices. Basta tomar como ejemplo el C5, es decir, el grafo ciclo de cinco vértices. Problema 4.- La mesa redonda. 4.1.- Un grupo de 9 personas se reúne todos los días alrededor de una mesa redonda. Queremos saber cuántos días podrán hacerlo de modo que cada nuevo día tengan al lado a dos personas diferentes. ¿Qué pasaría si fueran 10 personas? ¿Y un número cualquiera de personas?” Consideremos el grafo completo K9, que representa la mesa y todas las posibles relaciones entre sus miembros. Elegir una configuración en la mesa es equivalente a tomar un camino hamiltoniano sobre el grafo (es decir, uno que pase ¿Conocía Sherlock Holmes la Teoría de Grafos? Francisco M. Canto Martín, Juan Núñez Valdés y Serafín Ruiz Cabello REVISTA IBEROAMERICANA DE EDUCACIÓN MATEMÁTICA - JUNIO DE 2007 - NÚMERO 10 - PÁGINA 45 por cada vértice una y sólo una vez). Si dos caminos distintos comparten una arista, eso significa que en las dos configuraciones de la mesa que representan, hay dos personas juntas. Esto es lo que queremos evitar. La cuestión es entonces calcular cuántos caminos hamiltonianos disjuntos podemos encontrar en K9. Ya que éste posee en total 9 • 8 / 2 = 36 aristas y cada ciclo necesita 9, es inmediato ver que el máximo posible de configuraciones distintas es de 4. Una posible solución es: [1 2 3 9 4 8 5 7 6] – [1 3 4 2 5 9 6 8 7] – [1 4 5 3 6 2 7 9 8] – [1 5 6 4 7 2 8 3 9] Ahora veamos el caso de 10 personas. Ya sabemos cómo hay que operar. El K10 tiene 10 • 9 / 2 = 45 aristas y cada ciclo necesita 10, luego el máximo posible será 4 configuraciones distintas. Una posible solución sería: [1 2 3 10 4 9 5 8 6 7] – [1 3 4 2 5 10 6 9 7 8] [1 4 5 3 6 2 7 10 8 9] – [1 5 6 4 7 3 8 2 9 10] Es inmediato hacer los cálculos para un n cualquiera (excluyendo los casos triviales n = 1, 2 ó 3). En general, son posibles k soluciones distintas para n = 2k + 1 ó n = 2k + 2. 4.2.- Supongamos ahora que el grupo es de 12 personas, de las cuáles 6 son hombres y el resto, mujeres. Se desea sentarlos en una mesa redonda atendiendo a la misma regla del apartado anterior y teniendo en cuenta, además, que cada mujer debe estar sentada entre dos hombres y viceversa. ¿Cuántas configuraciones diferentes pueden darse? Este apartado es prácticamente similar al anterior, salvo que ahora trabajaremos con grafos bipartitos completos. En este caso particular, con el K6,6. Este grafo posee 36 aristas, y un ciclo hamiltoniano cualquiera comprende 12. Luego ya sabemos que, como máximo, habrá 3 configuraciones distintas, Y, en efecto, ésta es la solución pedida. A continuación se muestra una posible configuración: [M1 – H1 – M2 – H2 – M3 – H3 – M4 – H4 – M5 – H5 – M6 – H6] [M1 – H3 – M2 – H4 – M3 – H5 – M4 – H6 – M5 – H1 – M6 – H2] [M1 – H5 – M2 – H6 – M3 – H1 – M4 – H2 – M5 – H3 – M6 – H4] Problema 5.- El zorro, el conejo y la lechuga. Un pastor (P) necesita cruzar un río junto con sus tres pertenencias: un zorro (Z), un conejo (C) y una lechuga (L). Para ello dispone de una pequeña barca de remos en la que sólo cabe él junto con una sola de sus pertenencias. Sin embargo, no puede dejar solos en una misma orilla al mismo tiempo ni al zorro con el conejo, ni al conejo con la lechuga, para evitar una catástrofe. ¿Le será posible al pastor cruzar el río en estas condiciones? En caso afirmativo, dar los pasos que debe seguir. Éste es un problema clásico y muy conocido, y no es difícil comprobar que tiene solución, aunque deben darse palos de ciego hasta encontrarla. Sin embargo,