TEORIA 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 nn-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 Kn el grafo completo con n vértices, es decir en el cual cada par de vertices están conectadas por una arista. Kn,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 K3,3 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 K4 es planar (con tal de desviar la arista ab al exterior del cuadrado), que K5 no lo es en absoluto, y que K3,2 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 Kn es 1, y el de los Kn,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.
1.1. Introducción
Los siete puentes de Königsberg: Un ciudadano de Königsberg (Prusia) se propuso dar un paseo cruzando cada uno de los siete puentes que existen sobre el río Pregel una sola vez. Los dos brazos del río rodean a una isla llamada Kneiphof. ¿Cómo debe cruzar los puentes para realizar el paseo?
El problema es simplemente encontrar un trayecto, alrededor de una serie de puentes, que cruce solamente una vez cada uno de ellos. El mapa de abajo muestra la disposición de siete puentes y dos islas en la ciudad de Königsberg.
En 1736, el matemático suizo radicado en San Petersburgo Leonhard Euler publicó "Solutio Problematis ad Geometriam Situs Pertinentis", un artículo en el que resolvía el problema en el caso general. Este trabajo es considerado como el nacimiento de la Teoría de Grafos, utilizada hoy en día en múltiples aplicaciones
La idea de Euler fue considerar los cuatro lugares terrestres, que se deseaban comunicar (hay 4 de ellos), como puntos de destino y, a los famosos puentes, como trayectorias entre esos puntos. En consecuencia, el mapa de Königsberg –en esencia matemática– puede ser entonces reducido al siguiente diagrama, que es un ejemplo de lo que se suele llamar un grafo:
Un grafo, es una figura cuyas líneas o curvas (llamadas aristas), conectan puntos o vértices. En consecuencia, la trayectoria de los puentes de Königsberg puede ser reformulada como un grafo, en el cual las aristas son recorridas una sola vez. En la siguiente figura, los puntos rojos representan las áreas terrestres de Königsberg y las curvas negras los puentes. Este problema, por supuesto que puede ser resuelto mediante un estudio exhaustivo de todas las posibles trayectorias. Pero las matemáticas se interesan en generalizar el problema y buscar una solución sencilla y válida para todos los posibles mapas de ciudades, e incluso objetos más generales.
En función de la ubicación de cada uno de los vértices y de los puentes que los conectan, Euler demostró que no existe solución al problema de la trayectoria de los puentes de Königsberg.
Por lo general, usamos grafos en dos situaciones. En primer lugar, ya que un grafo es un modo muy conveniente y natural de representar las relaciones entre objetos: representamos objetos por puntos llamados vértices y la relación entre ellos por líneas llamadas aristas. En muchas situaciones (problemas) una representación de este tipo puede ser suficiente para ilustrar un problema.
Por ejemplo una molécula química puede representarse como un grafo donde los vértices son los átomos que la componen y las aristas, los enlaces entre estos átomos.


Otro ejemplo puede ser la representación de un mapa, en particular, el mapa de Colombia, donde los vértices representan los departamentos y cada arista une dos departamentos si estos tienen una frontera común.

En segundo lugar, tomamos el grafo como el modelo matemático, solucionamos el problema grafo-teórico apropiado, y luego interpretamos la solución en términos de problema original.
La mayor parte de los problemas de la teoría de grafo pueden ser clasificados en:
1. Problemas de Existencia
El problema de los siete puentes de Königsberg: Existe una trayectoria cerrada que cruce cada uno de los siete puentes exactamente una vez?
El problema del Caballo de Ajedrez: Existe una secuencia de los movimientos del caballo tal que visite cada cuadrado de un tablero de ajedrez exactamente una vez y regresando a la posición de partida?
El problema de los Cuatro Colores: Puede colorearse todo mapa con cuatro colores de modo que los países vecinos tengan colores diferentes?
2. Problemas de Construcción
Determinar si un grafo dado es euleriano y construir un camino euleriano (algoritmo de Fleury).
3. Problemas de Enumeración
Grafos etiquetados.
Digrafos etiquetados.
Árboles etiquetados.
4. Problemas de Optimización
Problema de encontrar el camino mínimo entre dos vértices en dígrafo pesado.
Problema del viajante de comercio
Enlaces:
www.astrocosmo.cl/anexos/p-p_konigsberg.htm
www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/graphIntro.htm