Teoría de los grafos
Keywords: Teoría de los grafos, Algoritmo, Azar, Circuito, Copyleft, GFDL, Glosario en teoría de grafos
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 unen algunos de ellos.
En la teoría de los grafos, sólo 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 vértices 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 vertices en forma de polígono regular da grafos muy legibles.
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 carreteras que conectan ciudades, una red eléctrica, un alcantarillado se pueden modelar 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, como el siguiente:
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 bidireccional, y corresponde a dos aristas orientadas.
Aquí V = { a, b, c, d, e }, y A = { (a,c), (d,a), (a,e), (b,e), (c,a),(c,c), (d,b) }.
Del vértice d sólo salen vértices: es una fuente. Al vértice e sólo entran vértices: es un agujero, o pozo.
Un ciclo es un camino, es decir una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices.
Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices 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.
Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda en bruto de todos los posibles caminos u otros métodos excesivamente costosos.
Un grafo que no tiene circuito y que conecta a todos los puntos, se llama un árbol:
En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles.
Los árboles son grafos que conectan vértices utilizando el menor número posible de aristas, de ahí su interés concreto.
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 sí 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 adyacentes 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 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. 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 ?
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 vértices 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 (se dice también plano), 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 diámetro de los Kn es 1, y el de los Kn,p es 2. Un diámetro infinito puede significar que el grafo tiene una infinidad de 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 escogemos dos paginas web al azar: ¿En cuántos clics se puede pasar de la primera a la segunda? El resultado es el diámetro de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son lógicamente 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.
(Ver también Glosario en teoría de grafos)
| Tabla de contenidos |
Aplicaciones
Gracias a la teoría de Grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Historia
El trabajo de Leonhard Euler sobre los puentes de Königsberg se considera el primer resultado de la teoría de los grafos. También se lo considera como uno de los primeros resultados topológicos en geometría; esto es, no depende de ninguna medida. Esto ilustra la conexión profunda entre la teoría de los grafos y la topología.
Véase también
Enlaces externos
- "Teoría de grafos" en la Enciclopedia Libre Universal en Español
- Grafos: Es un software para la construcción, edición y análisis de grafos. Forma parte de un proyecto (copyleft) de investigación y desarrollo de aplicaciones informáticas de diseño modular orientadas hacia la docencia, investigación y labores profesionales de Ingeniería de Organización Industrial (Management Engineering).
La primera versión de este artículo proviene de Enciclopedia Libre - Teor%C3%ADa_de_los_grafos, publicado bajo la licencia GFDL simple:Graph theory