El estudio de los grafos nació en 1736 cuando Leonhard Euler resolvió el problema de los siete puentes de Königsberg, introduciendo el uso de vértices y aristas para representar relaciones. Aquí se sentaron las bases de la teoría de grafos y su importancia en matemáticas e informática.
Un grafo es una estructura matemática que se usa para representar relaciones entre objetos.
Sus elementos son los vértices y aristas.
La valencia de un vértice es el número de aristas que inciden en él.
Existen muchos tipos de grafos como el grafo ciclo:
El grafo ciclo es el camino que empieza y termina en el mismo vértice.
Un grafo euleriano es un grafo que tiene un circuito euleriano, esto significa:
-Se pueden recorrer todas las aristas pasando por cada una de ellas una sola vez.
– Partimos y acabamo en el mismo vértice.
Muchos habréis jugado a dibujar esta casita sin levantar el lápiz ni repetir ninguna arista. Aquí tenéis una solución.
Esto se puede realizar en cualquier grafo si todas las valencias de sus vértices son números pares.
Un grafo semieuleriano es un grafo que tiene un camino euleriano pero no un circuito, es decir:
– Se pueden recorrer todas las aristas pasando por todas ellas una sola vez.
– Solamente se puede realizar empezando y terminando en vértices distintos (esos dos vértices podrían tener valencia impar, ninguno más)
Un grafo hamiltoniano es un grafo que tiene un ciclo hamiltoniano, es decir, un recorrido que visita todos los vértices exactamente una vez y vuelve al inicio
Usamos los grafos para tomar decisiones democráticas.
En una comarca se va a construir un hospital que pueda atender a los 8 pueblos principales que la forman.
Tenemos que decidir en qué pueblo construir el hospital tratando de ser justos en su elección, atendiendo a las distancias que habría que recorrer desde cada uno. ¿Hay alguna forma de comparar las distancias y poder decidir?
Sí, en teoría de grafos contamos con el algoritmo de Dijkstra que nos permite calcular todas las distancias desde un vértice (pueblo) a todos los demás.
Fuenteclara (A)
Seval (B)
Valleverde (C)
Encinar (D)
Ríar (E)
Altena (F)
Niole (G)
Jeval (H)
El algoritmo consiste en crear una tabla con todos los vértices en la que se van apuntando, sumando distancias y eligiendo el camino más corto para llegar a un vértice fijado. Además, el camino me indicará la distancia más corta. Así, podremos elegir democráticamente el pueblo en el que construir el hospital.
