Teoría de grafos

En matemáticas y en ciencias de la computación, la

teoría de grafos (también llamada teoría de las

gráficas) estudia las propiedades de los grafos

(también llamadas gráficas). Un grafo es un

conjunto, no vacío, de objetos llamados vértices (o

nodos) y una selección de pares de vértices,

llamados aristas (edges en inglés) que pueden ser

orientados o no. Típicamente, un grafo se representa

mediante una serie de puntos (los vértices)

conectados por líneas (las aristas).

HISTORIA

El trabajo de Leonhard Euler, en 1736, sobre el problema de los

puentes de Königsberg es considerado el primer resultado de la teoría

de grafos. También se considera uno de los primeros resultados

topológicos en geometría (que no depende de ninguna medida). Este

ejemplo ilustra la profunda relación entre la teoría de grafos y la

topología.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para

calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteó el problema de los cuatro colores que

plantea si es posible, utilizando solamente cuatro colores, colorear

cualquier mapa de países de tal forma que dos países vecinos nunca

tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang

Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos

definieron términos y conceptos teóricos fundamentales de los grafos.

Estructuras de datos en la representación de grafos.

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las

características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se

encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son

preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen

acceso rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista

• lista de incidencia - Las aristas son representadas con un vector de

pares (ordenados, si el grafo es dirigido), donde cada par representa

una de las aristas.[1]

• lista de adyacencia - Cada vértice tiene una lista de vértices los

cuales son adyacentes a él. Esto causa redundancia en un grafo no

dirigido (ya que A existe en la lista de adyacencia de B y viceversa),

pero las búsquedas son más rápidas, al costo de almacenamiento

extra.

En esta estructura de datos la idea es asociar a cada vértice i del grafo

una lista que contenga todos aquellos vértices j que sean adyacentes a

él. De esta forma sólo reservará memoria para los arcos adyacentes a i

y no para todos los posibles arcos que pudieran tener como origen i. El

grafo, por tanto, se representa por medio de un vector de n

componentes (si |V|=n) donde cada componente va a ser una lista de

adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo

indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para

mostrar el valor de la etiqueta.

Definiciones 

Vértice

Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de

las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.

Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo

pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

Grafo

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

Un grafo es una pareja de conjuntos ,

donde es el conjunto de vértices, y es el

conjunto de aristas, este último es un conjunto de

pares de la forma tal que . Para

simplificar, notaremos la arista como .

En teoría de grafos, sólo queda lo esencial del

dibujo: la forma de las aristas no son relevantes, sólo

importa a qué vértices están unidas. La posición de

los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Subgrafo

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice

que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las

necesidades de la situación).

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de

vértices de G.

Definición:

Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:

1- V’ V

2- A' A

3- (V’,A’) es un grafo

• Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

G2 es un subgrafo de G.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a

las aristas, por ejemplo, si se quiere representar la

red de las calles de una ciudad con sus direcciones

únicas. El conjunto de aristas será ahora un

subconjunto de todos los posibles pares ordenados

de vértices, con (a, b) ≠ (b, a). Los grafos que

contienen aristas dirigidas se denominan grafos

orientados, como el siguiente:

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas

orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece

también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Se considera la característica de "grado" (positivo o negativo) de un vértice (y se indica como ), como la 

cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3,

mientras que el grado negativo (llegadas) de d es 0.

Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo

máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene

grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el

caso anterior, el vértice e); tiene grado positivo 0. A continuación se presentan las implementaciones en maude de

grafos no dirigidos y de grafos dirigidos.En los dos casos, las especificaciones incluyen, además de las operaciones

generadoras, otras operaciones auxiliares.

Ciclos y caminos halmitoniamos

Un ciclo es 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 exactamente una vez (excepto el vértice del

que parte y al cual llega).

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 por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin

embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.

El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

Operaciones en grafos

Subdivisión elemental de una arista

se convierte en 

Se reemplaza la arista por dos aristas y un vértice .

Después de realizar esta operación, el grafo queda con un vértice y una arista más.

Eliminación débil de un vértice

Si y (Sea un vértice del grafo y de grado dos) eliminarlo débilmente significa reemplazarlo

por una arista que une los vértices adyacentes a .

se convierte en 

Entonces y desaparecen y aparece 

Árboles 

Un grafo que no tiene ciclos 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 n

n-2 árboles posibles. Su importancia radica en que los árboles son grafos

que conectan todos los vértices utilizando el menor número posible de aristas.

Un importante campo de aplicación de su estudio se encuentra en el análisis

filogenético, el de la filiación de entidades que derivan unas de otras en un

proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco

entre especies; aunque se ha usado también, por ejemplo, en el estudio del

parentesco entre lenguas.

Teorema de los cuatro colores 

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 toroide; el teorema siguiente no es válido:

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

qué país toca a qué 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 adyacentes. 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 han tenido que emplear 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, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en

algunos casos a plantearse la cuestión de que esta demostración y su aceptación es uno de los momentos que han

generado una de las más terribles crisis en el mundo matemático.

Coloración de grafos

Definición: Si G=(V, E) es un grafo no dirigido, una

coloración propia de G, ocurre cuando coloreamos

los vértices de G de modo que si {a, b} es una arista

en G entonces a y b tienen diferentes colores. (Por lo

tanto, los vértices adyacentes tienen colores

diferentes). El número mínimo de colores necesarios

para una coloración propia de G es el número

cromático de G y se escribe como C (G). Sea G un

grafo no dirigido sea λ el número de colores

disponibles para la coloración propia de los vértices

de G. Nuestro objetivo es encontrar una función

polinomial P (G,λ), en la variable λ, llamada

polinomio cromático de G , que nos indique el

número de coloraciones propias diferentes de los

vértices de G, usando un máximo de λ colores.

Descomposición de polinomios cromáticos. Si

G=(V, E) es un grafo conexo y e pertenece a Ε , entonces: P (G,λ)=P (G+e,λ)+P (G/e,λ), donde G/e es el grafo se

obtene por contracción de aristas.

Para cualquier grafo G, el término constante en P (G,λ) es 0

Sea G=(V, E) con |E|>0 entonces, la suma de los coeficientes de P (G,λ) es 0.

Sea G=(V, E), con a, b pertenecientes al conjunto de vértices V pero {a, b}=e, no perteneciente a al conjunto de

aristas E. Escribimos G+e para el grafo que se obtiene de G al añadir la arista e={a, b}. Al identificar los vértices a y

b en G, obtenemos el subgrafo G++e de G.

Grafos planos 

Cuando un grafo o multigrafo se puede dibujar en un

plano sin que dos segmentos se corten, se dice que

es plano.

Un juego muy conocido es el siguiente: Se dibujan

tres casas y tres pozos. Todos los vecinos de las

casas tienen 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.

Sea Kn 

el grafo completo con n vértices, Kn, p 

es el

grafo bipartito de n y p vértices.

El juego anterior equivale a descubrir si el grafo

bipartito completo K3,3 es plano, es decir, si se

puede dibujar en un plano sin que haya cruces,

siendo la respuesta que no. En general, puede determinarse que un grafo no es plano, si en su diseño puede

encontrase una estructura análoga (conocida como menor) a K5 o a K3,3.

Establecer qué grafos son planos no es obvio, y es un problema que tiene que ver con topología.

Diámetro 

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 páginas 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.