0

Redes y Grafos

Rafael Losada Liste, Jan 16, 2021

En un mundo global como el actual, abundan las conexiones entre objetos, personas y organismos. Estas conexiones forman a menudo una intrincada red cuyo análisis es fundamental para optimizar su funcionamiento y resolver problemas. Los modelos matemáticos de estas redes se fundamentan en la Teoría de Grafos. Un grafo no es más que un esquema de las conexiones de una red. Este libro te ayudará a sumergirte en el mundo de las redes y los grafos a través de diversos ejemplos y actividades que, de forma muy simplificada, recogen algunos términos y principios básicos.

Regiones, líneas y nodos
1. Introducción
2. Los puentes de Königsberg
3. Figuras de un solo trazo (sobre)
4. Un paseo por Sierpinski
5. Five room puzzle
Proximidad
1. Mediatriz y circuncentro
2. Diagrama de Voronoi
3. Voronoi a color
Soluciones prácticas
1. Introducción
2. Aplicaciones de los grafos
3. Conexiones de telefonía fija
Colores
1. Coloreando mapas y grafos
2. Teorema del mapa de cuatro colores
3. Número cromático
Geometría y grafos
1. El esqueleto de los poliedros
2. Grafos completos
3. Grafo completo K5
Número de caminos y potencias de matrices
1. Introducción
2. Número de caminos. Potencias de matrices
Actividades (pdf)
1. El recorrido de la señora marquesa
2. La tela de araña
3. Hojas de ejercicios
4. Soluciones de los ejercicios

Information

1.

Regiones, líneas y nodos

1. Introducción
2. Los puentes de Königsberg
3. Figuras de un solo trazo (sobre)
4. Un paseo por Sierpinski
5. Five room puzzle

1.1.

Introducción

Esta actividad pertenece al libro de GeoGebra Redes y Grafos. ¿Qué es una red? Piensa en las personas que conoces y te conocen, con las que hablas a menudo. Con cada una de ellas tienes una conexión, algo que no pasa con las demás personas. Pero, a su vez, cada una de esas personas, no solo te conoce a ti, conoce a otras, ya sean conocidas tuyas o no. A medida que empieces a expandir esta cadena de conocidos, surgirán más y más personas que tú no conoces directamente, pero con las que podrías comunicarte si supieses cuáles son las personas intermedias que te separan de ellas. Entre todas esas personas hay entonces una gran cantidad de conexiones, la gran mayoría de ellas desconocidas para ti. Decimos que el conjunto de todas esas personas y sus conexiones forman una red (en este caso, una red social). Si cambiamos las personas por ciudades y los reconocimientos por carreteras, obtenemos una red de carreteras. Si hablamos de teléfonos fijos y cables telefónicos obtenemos una red telefónica. Hay montones de cosas, personas, instituciones, hechos, símbolos, etc. que pueden interconectarse de diferentes modos. Cada uno de esos conjuntos de conexiones forma una red. ¿Qué es un grafo? Un grafo es un conjunto de puntos (vértices o nodos) y líneas que los conectan (aristas o arcos). El grado de un vértice es el número de aristas que concurren en él. Los grafos expresan las conexiones existentes en una red. Con el paso de los años, la Teoría de Grafos ha ido generando tantas aplicaciones que hoy se usa prácticamente en el análisis de cualquier red. ¿Cuándo y cómo aparecen los grafos? Comparativamente con otras áreas matemáticas, los grafos son bastante recientes. Surgen a partir de una curiosa pregunta planteada a principios del siglo XVIII en la ciudad rusa de Kaliningrado (entonces llamada Königsberg). El problema de los puentes de Königsberg se preguntaba si sería posible realizar un paseo andando sin salir de la ciudad, dividida en cuatro regiones por el río Pregolia, de modo que se recorriese una sola vez cada uno de los siete puentes que las conectaban. Este problema llama la atención del genial matemático Leonhard Euler, que estaba de visita en la ciudad, quien demuestra en 1736 que tal paseo es imposible de realizar. Esta demostración está considerada la cuna de la Teoría de Grafos. En ella, Euler conjuga tres grandes técnicas demostrativas.

Primero, sintetiza al máximo la situación, reduciendo cada una de las cuatro regiones del mapa de la ciudad a un punto y cada uno de los siete puentes a una línea, obteniendo lo que hoy se conoce como grafo dual del mapa, consistente en cuatro puntos unidos por siete líneas, como muestra la figura. De este modo, el problema original equivale a dibujar este grafo con un solo trazo, sin levantar el lápiz y recorriendo cada línea una sola vez. Segundo, Euler emplea un antiguo pero potentísimo método de demostración llamado reducción al absurdo. Euler sabe que habrá demostrado la imposibilidad del paseo si, razonando a partir de la suposición de que tal paseo existiera, alcanza una contradicción flagrante, un absurdo. Finalmente, para alcanzar esa contradicción, Euler aplica un criterio de paridad. El grafo tiene cuatro vértices. Como solo puede haber un vértice de salida y uno de llegada, los otros vértices tienen que ser vértices de tránsito, es decir, ni se empieza ni se acaba en ellos. Pero eso es imposible, ya que todo vértice de tránsito tendría que tener un número PAR de aristas (la mitad de ellas para llegar al vértice y la otra mitad para salir de él), y todos los vértices del grafo tienen grado impar (3 o 5). Así que… ¡el paseo buscado no puede existir! Los ciudadanos de Königsberg que lo intentaran estaban condenados de antemano al fracaso, como puedes comprobar en la siguiente actividad.

1.2.

1.3.

1.4.

1.5.

2.

Proximidad

1. Mediatriz y circuncentro
2. Diagrama de Voronoi
3. Voronoi a color

2.1.

Mediatriz y circuncentro

Esta actividad pertenece al libro de GeoGebra Redes y Grafos. La solución de Euler al problema de los puentes de Königsberg asocia un grafo a un mapa de regiones. En el siglo XIX surgen también problemas recíprocos, que parten de un conjunto de nodos y preguntan acerca de las regiones que deben corresponder a cierto criterio. Por ejemplo, dado un conjunto de nodos, ¿cuáles son las regiones formadas por todos los puntos más próximos a cada uno de ellos? Veamos primero los casos más sencillos, con dos y tres nodos. Observa la técnica que hemos empleado: contraemos simultáneamente circunferencias de diferentes colores pero del mismo radio con centro en cada nodo. El rastro de color de cada circunferencia solo sobrevivirá en la región más próxima a cada nodo.

Autor de la actividad y construcción GeoGebra: Rafael Losada.

2.2.

2.3.

3.

Soluciones prácticas

1. Introducción
2. Aplicaciones de los grafos
3. Conexiones de telefonía fija

3.1.

Introducción

Piensa en la red de carreteras de España. Son miles de caminos que conectan poblaciones y lugares. La red eléctrica también, solo que los enlaces son ahora cables en vez de carreteras. Análogamente, podemos pensar en la redes de autobuses o trenes, la red de metro de una ciudad (el de la figura corresponde a Madrid, año 1982), los circuitos eléctricos y electrónicos, las redes de fibra óptica e inalámbricas, las redes de suministro, las redes sociales, Internet (net significa red), la red de enlaces de los átomos en una molécula, etc. Nuestro propio cerebro alberga una red neuronal gracias a la cual podemos recordar, imaginar, pensar y sentir. En la actualidad existe ya toda una Ciencia de Redes y muchas herramientas que facilitan la creación y visualización de grafos. Los grafos tienden a expandirse de modo exponencial. A modo de ejemplo, en este enlace puedes visualizar el crecimiento del grafo correspondiente a contenidos de GeoGebra en unos siete años. Los grafos son esquemas de redes, que ayudan a analizarlas, independientemente de la naturaleza de los objetos conectados y sus conexiones. Algunos tienen estructura de árbol (solo hay un camino entre cada par de vértices), como los árboles genealógicos y los árboles de probabilidad:

3.2.

3.3.

4.

Colores

1. Coloreando mapas y grafos
2. Teorema del mapa de cuatro colores
3. Número cromático

4.1.

Coloreando mapas y grafos

Esta actividad pertenece al libro de GeoGebra Redes y Grafos. Fue una pregunta de coloreado de mapas la que impulsa definitivamente el desarrollo del estudio de los grafos. Esta pregunta, formulada en 1852 por un matemático inglés cuando aún era estudiante es: ¿será posible colorear cualquier mapa plano de regiones utilizando solo cuatro colores, de modo que no haya dos regiones vecinas del mismo color? La respuesta, afirmativa, se conoce como teorema de los cuatro colores, pero se tardó más de un siglo en poder demostrarlo. Por fin, en 1970 se obtiene la demostración. Aun así, si bien el resultado es aceptado por la comunidad matemática, la demostración invita a la polémica pues hace uso de un complejo programa de ordenador cuyos resultados no son verificables manualmente. ¿Surgirá algún día otro genio que consiga realizar una “elegante demostración más humana” de este teorema, al estilo de Euler? La coloración de grafos permite visualizar y analizar diferentes relaciones entre vértices conectados de un grafo. Por ejemplo, imagina que en una fiesta coinciden seis personas. Cada par de personas (hay 15 parejas posibles), o bien ya se conocen o bien son mutuamente desconocidas. Pues bien, un resultado conocido como Teorema de amigos y extraños, muy fácil de demostrar coloreando grafos, dice: “En cualquier grupo de seis personas, hay tres de ellas mutuamente conocidas o mutuamente desconocidas.” En la siguiente aplicación puedes intentar colorear pequeños mapas con el mínimo de colores posible (número cromático). Recuerda que dos regiones vecinas no pueden tener el mismo color. Esto equivale a colorear los vértices del grafo dual de modo que se diferencien los colores de cualquier par de vértices extremos de la misma arista.

Autor de la actividad y construcción GeoGebra: Rafael Losada.

4.2.

4.3.

5.

Geometría y grafos

1. El esqueleto de los poliedros
2. Grafos completos
3. Grafo completo K5

5.1.

El esqueleto de los poliedros

Esta actividad pertenece al libro de GeoGebra Redes y Grafos. Observa que, en el ejemplo del Five Room puzzle, el grafo correspondiente al puzle no es un grafo simple. Por el contrario, si proyectamos las aristas de cualquier poliedro sobre un plano, el grafo resultante es siempre un grafo simple. Esto es evidente, ya que dos vértices de un poliedro nunca se unen por más de una arista. Pues bien, se puede demostrar que este grafo resultante siempre es un grafo plano, es decir, podemos transformarlo en un grafo isomorfo en donde ningún par de aristas se corte (diagrama de Schlegel). En la siguiente construcción, intenta transformar el grafo simple, resultado de proyectar un icosaedro, en un grafo plano (es decir, intenta que las aristas no se corten). Para ello, activa la casilla Grafo y aplica este método: elige una región y coloca el resto de los vértices dentro. Hacia 1850 el matemático W. R. Hamilton patentó un juego que llamó Viaje por el Mundo. Consistía en encontrar un recorrido que pasase por 20 ciudades situadas en los nodos del grafo del dodecaedro (que es equivalente a un recorrido por los 20 vértices del dodecaedro). Desde entonces, se llaman caminos hamiltonianos a los recorridos que visitan todos los vértices de un grafo una sola vez (en los caminos eulerianos, era cada arista la que se recorría una sola vez). Puedes intentar encontrar un camino hamiltoniano en el icosaedro de la construcción. También puedes intentar resolver el juego original de Hamilton (elige dodecaedro en vez de icosaedro). En ambos casos, si activas la casilla Cadena podrás ayudarte de la cadena roja para señalar el recorrido.

Autor de la actividad y construcción GeoGebra: Rafael Losada.

5.2.

5.3.

6.

Número de caminos y potencias de matrices

1. Introducción
2. Número de caminos. Potencias de matrices

6.1.

Introducción

Grafos bipartitos completos En un grafo completo, todo vértice se conecta a todos los demás. Si previamente dividimos los vértices en dos grupos (como si estuviesen enfrentados), podemos pensar en el grafo que conecta cada vértice de un grupo con todos los vértices del otro grupo. Un grafo así se denomina bipartito completo. Un ejemplo muy conocido de este tipo de grafos es el que plantea el famoso problema de las tres casas y los tres servicios (K_3,3). Se trata de conectar tres casas con tres fuentes de suministros (agua, luz y gas), sin que las conexiones se entrecrucen. En la ampliación de la actividad 4 del cuadernillo de actividades "La tela de araña" verás un razonamiento que demuestra que tal grafo no es posible en el plano, pero sí en otras superficies (puedes intentarlo en las hojas de ejercicios).

En el apartado anterior, tal vez hayas llegado a la conclusión correcta de que un grafo completo de n vértices (K_n) tiene siempre n(n-1)/2 aristas. ¿Sabrías ahora averiguar cuántas aristas tiene un grafo bipartito completo K_n,mde "n" vértices de un grupo conectados con todos los "m" vértices de otro grupo? Por ejemplo, K_3,3 tiene 9 aristas. Matriz de adyacencia La información recogida en un grafo también se puede expresar mediante números, lo que facilita los cálculos computacionales en grandes redes. Por ejemplo, la información del grafo de los puentes de Königsberg puede recogerse en una matriz, llamada matriz de adyacencia.

Cada fila de la matriz representa el número de aristas que comparte un vértice con cada uno de los vértices. La suma de todos los números de una fila es el grado del vértice correspondiente. Nota: Observa que la matriz es simétrica, ya que si una arista conecta A con B, también conecta B con A. Sin embargo, hay grafos (llamados grafos dirigidos) en donde cada arista tiene una orientación, de modo que A puede conectar con B pero no al revés. En ese caso, la matriz de adyacencia no será simétrica.

0

Redes y Grafos

Table of Contents

Information

Regiones, líneas y nodos

Introducción

Proximidad

Mediatriz y circuncentro

Soluciones prácticas

Introducción

Colores

Coloreando mapas y grafos

Geometría y grafos

El esqueleto de los poliedros

Número de caminos y potencias de matrices

Introducción

Actividades (pdf)

El recorrido de la señora marquesa

¿Sabrías resolver este pequeño misterio?