¿Qué es la Teoría de Grafos, y cómo se define un grafo como tal?

Alexander Barraza
Graduado en Física, UNAL

En 1736, a partir de los trabajos del físico-matemático suizo Leonhard Euler (1707-1783), se establece que una sucesión de vértices define un camino, no obstante, si dicho camino consiste en diferentes vértices sin repetir aristas se denomina como trayectoria o camino euleriano; si adicionalmente llegamos al punto de partida, recorriendo cada arista una sola vez, tenemos entonces un ciclo (circuito) euleriano.

Por su parte, definimos un grafo como un par ordenado (V, A) donde V designa al conjunto (no vacío) de todos los vértices o nodos de un grafo, mientras que A designa al conjunto (puede ser vacío) de todas las aristas o líneas que unen los vértices de un grafo. Los elementos del conjunto A pueden designarse como un par no ordenado {v, w} donde v y w son elementos (nodos o vértices) de V, de esta forma se dice entonces que v y w son vértices adyacentes (están unidos por una arista).

La teoría de grafos surge a partir la respuesta dada por Euler ante una problemática del ingenio popular que se preguntaba cómo recorrer los siete puentes que unían dos islas de la comunidad de Königsberg (parte de Alemania en su época, y actualmente Kaliningrado, en Rusia), entre ellas y con tierra firme sin usar dos veces un mismo puente y llegando al punto de partida (ubicado en tierra firme) cualesquiera que este sea, determinando que en este caso, en definitiva, no se podía.

¿Cómo se aborda el problema de los siete puentes de Königsberg?

Se lo modela como un grafo donde cada punto (vértice o nodo) representa un puente y cada línea (arista) un camino por tierra firme:

¿Existe una solución a este problema?

No hay solución capaz de cumplir las condiciones impuestas, puesto que, como demostró Euler, los vértices no son de grado par, esto es, no incide un número par de líneas a cada punto (número de aristas que salen o llegan de dicho vértice). No parece que podamos hacer mucho con una estructura definida de una forma tan simple como esta, sin embargo, como suele suceder en las matemáticas, a veces las cosas no son lo que parecen. Así, se origina una de las áreas más prolíficas, transversales e interdisciplinares del conocimiento humano, la teoría de grafos.

¿Grafos eulerianos o con trayectoria euleriana?

Los siguientes grafos tienen todos caminos eulerianos _[2]. ¿Tienen todos ciclos eulerianos?

Tomemos el tercer grafo, sobre el cual numeremos los vértices:

Vemos entonces que el camino definido por la sucesión {3,4,6,2,1,3,7,6,5,4,2} es un camino euleriano, pues se recorre todo el grafo sin repetir aristas, pero no es un ciclo euleriano, ya que no llega al punto de partida. ¿Qué hubiese pasado si numeramos los vértices de manera distinta? No mucho, salvo que ahora el camino sería definido por una sucesión distinta. ¿Qué hubiese pasado si seguimos caminos distintos al planteado en nuestra solución inicial? Esta pregunta sí es un poco más compleja de responder, e involucra algoritmos con los cuales suelen estar encantados los ingenieros de programación.

Para una demostración más rigurosa de lo aquí expuesto tenemos que remitirnos al siguiente resultado:

Podemos entonces verificar que en efecto en el grafo que tomamos solo los vértices 3 y 6 tienen grado impar (esto ocurriría aún si la numeración de vértices hubiese sido distinta), por lo tanto dicho grafo tiene un camino euleriano _[4]. Para los grafos restantes podemos proceder de manera análoga y verificar si, en efecto, tienen caminos y ciclos eulerianos, o dicho de otra manera, ¿podemos trazar dichos grafos sin levantar el lápiz y repetir líneas? La respuesta a este interrogante se deduce de lo ya expuesto hasta el momento, sin embargo, constituye un ejercicio interesante en cuanto a motricidad fina, ingenio y paciencia, a lo que invito al lector a encontrar y trazar grafos de 6 o más vértices con trayectoria euleriana.

¿Existen otros tipos de grafos? ¿La teoría de grafos tiene aplicaciones en el mundo ‘real’?

Estos grafos que hemos revisado muy someramente, son solo uno de los tantos tipos de grafos que encontramos en la teoría de grafos. También podemos encontrar grafos tales como árboles, muy representativos en conjuntos donde sus elementos pueden clasificarse en jerarquías y en cálculos de conteo y probabilidad _[5], dígrafos, grafos hamiltonianos _[06], etc.

Estos enigmas, si así los queremos llamar, tienen una aplicabilidad enorme en el mundo actual, en situaciones tan diversas como: biología molecular _[07], informática _[08], telecomunicaciones _[09] y análisis de redes _[10]. Cabe preguntarse entonces: ¿No resulta cuando menos curioso que un problema de naturaleza casi banal terminara siendo uno de los resultados más interesantes y conspicuos de las matemáticas? Quizás, para ello, era necesario el aporte de una de las mentes más preclaras de la humanidad.

Por: Alexander Barraza. Graduado en Física por la Universidad Nacional de Colombia. Tutor, docente universitario. Entiende que lo cognitivo y lo emocional son aspectos vitales en los procesos de enseñanza-aprendizaje.

Trabajo publicado en: Jul., 2022.

Datos para citar en modelo APA: Barraza, A. (julio, 2022). Definición de Teoría de Grafos. Significado.com. Desde https://significado.com/teoria-grafos/