Teoría de grafos

La teoría de grafos tiene su origen en el problema de los siete puentes de Königsberg resuelto por Leonhard Euler.

Más tarde, otros problemas influyeron en el desarrollo de la teoría de grafos como el estudio de las redes eléctricas, la enumeración de isómeros de hidrocarburos,...

Hoy en día es rara la disciplina científica o humanística que no utiliza la teoría de grafos. Como ejemplos podemos citar la psicología en dinámica de grupos, la sociología en los sociogramas, la física teórica, que usa los diagramas de Feynmann, donde se representan mediante líneas las partículas elementales, el estudio de flujos en redes en programación lineal e investigación operativa, los cambios de variable en el cálculo diferencial...

Dibujar un grafo para resolver un problema es un reflejo muy común, que no precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y consta de vértices y de aristas que reúnen algunos de ellos.

En la teoría de los grafos, sólo se queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importan sus extremidades (o cabos); la posición de los vertices tampoco, y se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy leíbles.

Formalmente: Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, la arista {a,b} se denota ab.

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Una red de autovías que conectan ciudades, una red elétrica, un alcantarillado se pueden modelizar con grafos.

En algunos casos es necesario imponer un sentido a las aristas, por ejemplo si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Las aristas son entonces pares ordenados de vértices, con (a,b) ≠ (b,a), y se define así grafos orientados (figura a la izquierda).
En este grafo se ha autorizado una arista que tiene sus dos cabos idénticos: es un rizo (o bucle), y aparece también una arista sin flecha: significa que la arista se puede recorrer en cualquier sentido: es bidirreccional, y corresponde o dos aristas orientadas.

En el ejemplo, V = { a, b, c, d, e }, y A = { (a,c), (a,d), (a,e), (b,e), (c,a),(c,c), (d,b) }.

Del vértice d sólo salen aristas: es una fuente. Del vértice e sólo entran aristas: es un agujero, o pozo.

Un ciclo es un camino, es decir una sucesión de aristas adyacientes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todas los vértices.

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sóla vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vertices son las salas, y las aristas los corredores o puertas entre ellas).

Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada.

Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. La figura muestra un ciclo hamiltoniano en el grafo del dodecaedro.

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano.

Un grafo que no tiene circuito y que conecta a todos los puntos, se llama un árbol.

En un grafo con n vertices, los arboles tienen exactamente n - 1 aristas, y hay n^n-2 árboles posibles. Los árboles son grafos que conectan vertices utilizando el menor número posible de aristas, de ahí su interés concreto, por ejemplo en las líneas eléctricas o telefónicas.

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado. Formalmente, es un grafo con una función v: A → R₊.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre si por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas. Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacientes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toro; el teorema siguiente no es válido:

Teorema de los cuatro colores: Cuatro colores son siempre suficientes para colorear el un mapa.

El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber cual país toca cual otro.

Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacientes (figura derecha). Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. prueba de ello es que se ha tenido que emplear los ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador.

Un juego muy conocido es el siguiente: Se dibuja tres casas y tres pozos. Los vecinos de las casas tienen todos el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces?

Pues no: cualquier disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce. Se nota K_n el grafo completo con n vértices, es decir en el cual cada par de vertices están conectadas por una arista. K_n,_p es el grafo compuesto de un grupo de nvértices y otro de p, tal que cada vértice del primer grupo está conectado con cada del segundo, y no hay más aristas.

El juego anterior equivale a descubrir si el grafo K₃,₃ es planario, es decir si se puede dibujar en un plano sin que haya cruces. Y la respuesta es no.

Establecer qué grafos son planarios no es obvio, y tiene que ver con la topología.

En la figura, se nota que K₄ es planar (con tal de desviar la arista ab al exterior del cuadrado), que K₅ no lo es en absoluto, y que K₃,₂ lo es también (desvíos en gris).

En un grafo, La distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en una figura como en un grafo, es la mayor distancia entre dos puntos de la misma. El dimetro de los K_n es 1, y el de los K_n,_p es 2. Un diametro infinito puede significar que el grafo tiene una infinidad e vértices o simplemente que no es conexo. También se puede considerar el diámetro promedio, como el promedio de las distancias entre dos vértices.

El mundo de Internet ha puesto de moda esa idea del diámetro: Si descartamos los sitios que no tienen enlaces, y escojamos dos paginas güeb al azar: ¿En cuántos cliques o clics se puede pasar de la primera a la segunda? El resultado es el diametro de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son logicamente los enlaces.

En el mundo real hay una analogía: tomando al azar dos seres humanos del mundo, ¿en cuántos saltos se puede pasar de uno a otro, con la condición de sólo saltar de una persona a otra cuando ellas se conocen personalmente? Con esta definición, se estima que el diámetro de la humanidad es de ... ¡ocho solamente!

Este concepto refleja mejor la complejidad de una red que el número de sus elementos.

Autor: M.Romero Schmidtke