Categoría: Tema 2. Fundamentos y aplicaciones de la teoría de grafos. Diagramas en árbol.

En esta entrada voy a desarrollar el segundo tema de la oposición de Matemáticas de Secundaria; que no es otro que los fundamentos y aplicaciones de la teoría de grafos y los diagramas en árbol.

La preparación de las oposiciones de Matemáticas no es fácil precisamente, como tampoco lo son la resolución de las partes prácticas de las Comunidades Autónomas. Con estos artículos pretendo ayudar en la medida de lo posible a aquellos opositores que hayan decidido hacerlo. 

El desarrollo lo he concretado en siete vídeos de diversa duración; aunque es cierto que uno de ellos, el séptimo exactamente, tiene una extensión de algo más de una hora. Podría haberlo cortado en dos o tres vídeos y haber tenido entonces un total de diez más o menos. Sin embargo, dividir la demostración de un teorema en partes no es algo que me guste mucho; y al final he pensado que era mejor dejarlo íntegramente en uno solo.

El tema tiene dos partes bien diferenciadas: una primera con la teoría de grafos, y la segunda una caracterización de un tipo de grafo concreto, los árboles.

Para la primera parte, el desarrollo propio de la teoría de grafos, he grabado cinco vídeos. En ellos defino los grafos, los tipos de grafos y luego hago un estudio más o menos exhaustivo de los grafos eulerianos y de los grafos hamiltonianos.

La segunda parte, la de los diagramas en árbol, se desarrolla en dos vídeos. Uno primero de duración más corta, con definiciones básicas, en la que demuestro un resultado necesario para la caracterización de los árboles; y una segunda de más de una hora, en la que caracterizo dichos árboles.

Definiciones

Un grafo podría definirse como la representación en un plano de una serie de puntos y de las líneas que unen dichos puntos. A éstos se les denomina vértices y a ellas aristas. Las aristas pueden ser dirigidas y el grafo se denomina grafo dirigido. Todas estas definiciones y algunas más las podéis encontrar en el primer vídeo y en los sucesivos.

La teoría de grafos se considera predecesora de otras ramas muy importantes de la Matemática, como la Topología; y como aplicación en ramas de la ciencia, de la información de los transportes, etc.

Grafos Eulerianos. Definiciones

La mayoría de los autores consideran el problema de los puentes de Königsberg como el origen de la teoría de grafos. Dicho problema se planteo a principios del siglo XVII. La ciudad de Königsberg, actualmente Kaliningrado, que fue anexionada por la URSS al finalizar la II Guerra Mundial, y ahora pertenece oficialmente a la exrepública Rusia, tiene siete puentes que cruzan en distintas partes del río Pregel. El problema o juego consistía en encontrar un camino que cruzara dichos puentes sin repetir ninguno de ellos.

Podéis ver el dibujo esquemático del problema.

Euler resolvió el problema de los siete puentes restringiéndolo a un problema de teoría de grafos.

La resolución, como muchas del gran matemático alemán, contiene ideas brillantes pues lo reduce básicamente a la paridad de los vértices. La idea que subyace detrás, y que es el inicio de la teoría de grafos, es poco menos que brillante.

Sin embargo no fue Euler el que caracterizó los grafos que posteriormente llevaron su nombre. Se considera un grafo euleriano aquel que contiene un circuito euleriano; y un circuito euleriano es aquel que pasa por todas las aristas recorriendo cada una de ellas una sola vez; siendo un circuito un camino que empieza y acaba en el mismo vértice.

Grafos Eulerianos. Caracterización

El teorema que determina aquellos grafos que contienen un circuito que pase por todas las aristas una única vez es debido a Carl Hierholzer, matemático alemán de mediados del siglo XIX. Hierholzer demostró, en 1971, que la condición necesaria y suficiente para que un grafo conexo contenga un circuito que pase por todas las aristas una única vez es que todos los vértices sean de grado par.

Euler solo demostró la condición necesaria aunque aparentemente llegó a enunciar la suficiente sin demostrarla. Es curioso sin embargo que dicha condición necesaria sea suficiente para demostrar la imposibilidad de la existencia de un camino en el problema de los puentes de Königsberg.

Grafos Hamiltonianos

Como tipo de grafo también de cierta importancia se encuentran los grafos hamiltonianos. Dichos grafos son aquellos que contienen un ciclo hamiltoniano; y un ciclo de estas características es un camino que comienza en un vértice y pasa por todos los vértices restantes sin hacerlo dos veces por ninguno de ellos.

Al igual que con los grafos eulerianos, la atribución de este tipo de grafos se debe al matemático Sir William R. Hamilton, pero lo cierto es que no fue éste sino T. P. Kirkman el primero que investigó tales grafos. Aunque sí fue Hamilton el que diseñó el juego “El dodecaedro del viajero”, o “El viaje alrededor del mundo”. Dicho juego constaba de un dodecaedro sólido donde los vértices representaban veinte ciudades importantes de la época. El juego consistía en trazar un recorrido a través de las aristas del dodecaedro, pasando una única vez por cada ciudad.

Diagramas en árbol. Definiciones

En la segunda parte del tema defino y desarrollo los diagramas en árbol. Un grafo se dice que es un árbol si es conexo y no tiene circuitos. El concepto de diagrama en árbol se asemeja bastante a nuestra idea intuitiva de lo que es un árbol.

Caracterización de los árboles

En los dos últimos vídeos doy algunas definiciones básicas y demuestro un teorema que caracteriza de alguna forma los árboles.