¿Qué es un grafo?
Un grafo es una forma sencilla de representar relaciones usando puntos llamados vértices y líneas llamadas aristas, que los conectan entre sí, como si fuera un mapa.
Los vértices pueden representar personas, lugares o equipos, y las aristas muestran cómo están relacionados, por ejemplo, una amistad, una carretera o una ruta. La valencia o grado de un vértice señala cuántas conexiones tiene, es decir, cuántos caminos o aristas salen de él.
Hay grafos dirigidos, que usan flechas, y grafos no dirigidos, como una carretera de doble sentido. También existen grafos simples, completos o conexos, según cómo estén unidos sus puntos, y se usan en la vida diaria en mapas, redes sociales, rutas de transporte y problemas de matemáticas para entender mejor cómo funciona todo.
¿Donde surgieron los grafos?
Hace unos siglos, en una ciudad llamada Königsberg, había 7 puentes que unían diferentes zonas. La gente se preguntaba:
¿Es posible cruzar todos los puentes exactamente una vez sin repetir ninguno?
Era un juego de lógica muy popular entre los habitantes.
Un matemático llamado Euler se dio cuenta de que dibujar la ciudad completa era demasiado complicado, así que decidió simplificarla:
- Cada zona de la ciudad → un punto (vértice).
- Cada puente → una línea que conecta esos puntos (arista).
Sin darse cuenta, Euler inventó la idea básica de los grafos, que hoy son dibujos con vértices y aristas que representan conexiones.
Así, los grafos nacieron a partir de un acertijo que parecía un juego. Euler resolvió el problema en 1736 usando estos puntos y líneas para representar la ciudad de manera sencilla.
Ese mismo método que él creó hoy se usa en matemáticas, informática, redes sociales, mapas y mucho más.
¿Qué son los grafos eulerianos y semieulerianos?
Un grafo euleriano es aquel que tiene un circuito que recorre todas sus aristas exactamente una vez.
Para que un grafo sea euleriano, todos sus vértices deben tener un número par de conexiones. Por ejemplo, un ciclo con 4 vértices cumple esta condición y es euleriano, mientras que el famoso caso de los 7 puentes de Königsberg no lo es.
Por otro lado, un grafo semieuleriano también permite recorrer todas sus aristas sin repetir ninguna, pero en este caso el recorrido comienza en un vértice y termina en otro distinto. Para que un grafo sea semieuleriano, debe estar conectado y tener exactamente dos vértices con un número impar de conexiones. Si un grafo tiene más de dos vértices impares, no es ni euleriano ni semieuleriano.
Este es el grafo euleriano mas conocido:
¿Qué es un grafo hamiltoniano?
Un grafo hamiltoniano es un grafo conectado en el que se puede hacer una vuelta completa, pasando por todos los vértices una sola vez y regresando al punto de inicio. Es como dar una vuelta por varios lugares sin repetir ninguno, formando un gran círculo. En este caso, no importa si no se recorren todas las aristas; lo importante es visitar cada vértice una vez. Por ejemplo, un ciclo de 5 vértices o un grafo completo con más de dos vértices son hamiltonianos, porque permiten hacer ese recorrido sin repetir puntos.
La diferencia con un grafo euleriano es que este se intenta recorrer todas las aristas exactamente una vez, aunque se repitan vértices. En cambio, el grafo hamiltoniano se centra en pasar una sola vez por cada vértice, sin importar cuántas conexiones queden sin usar.
¿Grafos y democracia?
¿Pueden utilizarse los grafos y aplicarse con fines democráticos?
A mi pueblo han venido muchos equipos de fútbol de primera división para hacer propaganda, vender camisetas e intentar que la gente se asocie a su equipo.
Yo quiero pasar por todas las calles que han formado y que uen los distintos puestos para ver qué me ofrecen pero sin repetir ninguna para no perder tiempo.
Para representarlo con grafos, cada puesto se convierte en un vértice, y cada calle que conecta dos de esos puestos se convierte en una arista.
Para que pudiera pasar por cada calle exactamente una vez y volver al inicio, el grafo debe ser conexo y euleriano, lo que significa que todos los vértices deben tener grado par permitiendo un circuito que recorra todas las aristas sin repetir injustamente ninguna.
¿Es euleriano esta disposición? Compruébalo y busca el recorrido
