Fundamentos y aplicaciones de la teoría de grafos | Diagramas en árbol – Temario secundaria. Dentro de los muchos temas que se deben estudiar para las oposiciones de enseñanza secundaria, el de grafos y matrices es quizás uno de los más complejos, de modo que vamos a explicarlo a continuación por partes y con todo detalle para que puedas estudiarlo sin problema.
Qué es un grafo y tipos
Un grafo (del griego grafein, trazar) es una forma de representar de una manera cómoda las posibles relaciones entre objetos.
Pongamos como ejemplo el que Juan está planeando un viaje por carretera desde su ciudad a la casa de un amigo unas pocas ciudades más allá. Juan tendrá varias rutas diferentes para elegir, cada una de ellas pasando por diferentes ciudades vecinas.
Por ello, Juan decide crear un mapa representando las ciudades como puntos, y pone líneas entre ellas que representan la ruta para llegar de una a la otra. También incluye cuántos kilómetros tiene cada ruta al etiquetar los bordes con su distancia.
En matemáticas, llamamos a este mapa que Juán creó un grafo. Un grafo es una colección de puntos, llamados vértices, y líneas entre esos puntos, llamadas aristas. Hay muchos tipos diferentes de grafos en las matemáticas de modo que veamos cuáles podemos encontrar:
Tipos de grafos
Aunque hay muchos tipos diferentes de grafos en el campo de las matemáticas, hay algunos que son extremadamente comunes. Algunos de esos son los siguientes:
- Grafo nulo: también llamado grafo vacío, es un grafo en el que no hay aristas entre ninguno de sus vértices.
- Grafo conectado : un grafo en el que hay una ruta de aristas entre cada par de vértices en el grafo. El grafo de Juan es un grafo conectado, ya que hay una manera de llegar desde cada ciudad del mapa a cualquier otra ciudad.
- Grafo desconectado : un grafo en el que la ruta de las aristas no siempre conecta todos los vértices.
- Grafo bipartito : un grafo que se puede dividir en dos conjuntos de vértices de modo que las aristas solo vayan entre conjuntos, no dentro de ellos.
- Grafo ponderado : un grafo en el que se asignan pesos o valores numéricos a cada una de las aristas. El grafo de Juan es también un grafo ponderado, donde las distancias entre las ciudades son los pesos de los bordes.
- Grafo dirigido : un gráfico en el que las aristas están dirigidas por flechas, lo que indica que la relación, representada por la arista, solo se aplica de un vértice al otro, pero no al revés. En otras palabras, si una arista dirigida tiene una flecha de A a B, A está relacionada con B, pero B no está relacionada con A.
- Grafo no dirigido : un grafo cuyas aristas no están dirigidas. El grafo de Juan es un grafo no dirigido, porque las rutas entre ciudades van en ambos sentidos.
- Grafo simple : un grafo no dirigido en el que hay como máximo una arista entre cada par de vértices, y no hay bucles , que es una arista desde un vértice hacia sí mismo.
- Multi-grafo: Un grafo en el que hay múltiples aristas entre cualquier par de vértices o hay aristas desde un vértice hacia sí mismo, también llamado bucle.
- Grafo plano : un grafo que se puede dibujar para que todas las aristas del grafo no se crucen entre sí.
- Grafo no plano : un grafo que no es un grafo plano. En otras palabras, un grafo que no se puede dibujar sin al menos un par de aristas cruzadas.
Operaciones entre grafos
Varias son las operaciones que se pueden dar entre grafos pero principalmente, estas se realizan para el manejo de estructuras de datos, de modo que para que veáis como se desarrollan, nos centramos en las de este campo. Dentro de las operaciones entre grafos para hacer estructuras de datos, las básicas serían las de insertar y borrar es decir, operaciones en las que vemos como se insertan o eliminan vértices o también se insertan o eliminan aristas.
Estas son las operaciones principales entre grafos:
Insertar vértice
Cuando se realiza la inserción de un nuevo vértice lo único que se hace es añadir una nueva entrada en la tabla de vértices creada para el nuevo nodo. De este modo, el grafo mostrará un vértice más, inicialmente aislado, dado que no habrá ninguna arista que llegue hasta él.
Insertar arista
Consiste en insertar una nueva línea o arista en el grafo, de manera que habrá añadir también un nuevo nodo a la lista de adyacencia, que es la lista en la que están almacenados los nodos a los que puede acceder un vértice a través de una arista. De este modo, en el caso de añadir la arista A-C, se tiene que incluir también en la lista de adyacencia que va de A al vértice C como nuevo destino.
Eliminar vértice
En esta operación se procede con la eliminación de la tabla de vértices del vértice en sí. Para ello además se tienen que eliminar las aristas que formaran parte del vértice borrado.
Eliminar arista
En esta operación se elimina un arco del grafo, de modo que tenemos que borrar la lista de adyacencia del vértice o nodo de origen y el nodo correspondiente al nodo destino.
Otras operaciones
Otras operaciones entre grafos pueden ser la búsqueda de un elemento o recorrido del grafo, así como la ejecución de algoritmos para unir dos vértices en un recorrido más corto del grafo.
Matrices y grafos
Una vez ya hemos visto qué son los grafos, que recordamos que son una combinación de vértices (nodos) y aristas pero además, los grafos se pueden convertir en una matriz, que es una colección de números organizados en un número fijo de filas y columnas. Por lo general, los números son números reales.
De este modo, todo grafo, dirigido o no, puede representarse mediante una matriz que será cuadrada y que tendrá como orden el número de vértices del grafo. Dicha matriz recibe el nombre de matriz asociada o matriz de adyacencia
Ejemplos de matrices de adyacencia
1) Construcción de la matriz de adyacencia de un grafo no dirigido:
Para construir las matrices de adyacencia, ordenamos los vértices tal y como se puede ver en el siguiente ejemplo:
Cuando se nos presenta una arista que une los vértices a y b, en la matriz de adyacencia tenemos que poner un 1 tanto en la posición ab como en la posición ba.
La matriz de adyacencia de los grafos no dirigidos siempre es simétrica.
2) Construcción de la matriz de adyacencia de un grafo dirigido:
Para construir las matrices de adyacencia, ordenamos los vértices como vemos en este otro ejemplo:
Si tenemos una flecha que sale del vértice a y llega al vértice e , ponemos un 1 en la posición ae de la matriz de adyacencia. En caso de no tener esa flecha ponemos un 0.
La matriz de adyacencia de un grafo no dirigido no tiene por qué ser simétrica.
3) Escribamos las matrices de adyacencia o asociadas a cada uno de los siguientes grafos:
Diagramas en Árbol
Por últimos tenemos que hablaros de los diagramas en árbol que son las formas más poderosas y efectivas de representar un grafo. Dentro de ellos nos podemos encontrar árboles de búsqueda binarios de los que es importante saber cómo funcionan y cómo hacen que las visualizaciones sean más interpretables. Pero antes de todo eso, hemos de tomarnos un momento para comprender qué son los árboles en este contexto.
Los árboles son gráficos que no contienen ni un solo ciclo:
En el ejemplo anterior, el primer grafo no tiene ciclo (también conocido como un árbol), mientras que el segundo grafo tiene un ciclo por lo tanto, no es un árbol.
Los elementos de un árbol se llaman nodos. (A, B, C, D y E) son los nodos en el árbol anterior. El primer nodo (o el nodo superior) de un árbol se conoce como nodo raíz, mientras que el último nodo (nodo C, D y E en el ejemplo anterior) se conoce como nodo hoja. Todos los nodos restantes se conocen como nodos secundarios (nodo B en nuestro caso).
Es hora de pasar a uno de los temas más importantes de la teoría de grafos relacionada con los diagramas en árbol, es decir, la transversal de grafos.
Recorrido del grafo
Supongamos que queremos identificar la ubicación de un nodo en particular en un grafo. ¿Cuál podría ser la posible solución para identificar nodos de un grafo? ¿Cómo empezar? ¿Cuál debería ser el punto de partida? Una vez que conocemos el punto de partida, ¿cómo proceder más? Podemos responder a todas estas preguntas en esta sección explicando los conceptos de trasversal de grafos.
Un recorrido de grafo se refiere a visitar cada vértice y arista de un grafo exactamente una vez en un orden bien definido. Como el objetivo del recorrido es visitar cada vértice solo una vez, mantenemos una pista de vértices cubiertos para que no cubramos el mismo vértice dos veces. Existen varios métodos para el recorrido de grafos así que podemos ver algunos de los métodos famosos:
Búsqueda en anchura:
Comenzamos desde el nodo fuente (nodo raíz) y atravesamos el grafo, en capas. Los pasos para este algoritmo son:
- Primero muévete horizontalmente y visita todos los nodos de la capa actual.
- Muévete a la siguiente capa y repite los pasos anteriores.
Podemos representar este árbol de la siguiente manera:
Profundidad primera búsqueda
Veamos primero los pasos involucrados en este enfoque:
- Primero seleccionamos el nodo fuente y almacenamos todos sus nodos adyacentes.
- Luego recogemos un nodo de los nodos almacenados y almacenamos todos sus nodos adyacentes.
- Este proceso se repite hasta que no haya ningún nodo disponible.
La secuencia para la búsqueda de profundidad primero para el ejemplo anterior será:
A -> B -> D -> E -> C -> F
Árbol de búsqueda binaria
En este enfoque, todos los nodos de un árbol están dispuestos en un orden ordenado. Echemos un vistazo a un ejemplo:
Artículos de interés: