Grafo

Definiciones Basicas

Grafo: Un grafo G es una dupla G = (X, U), donde X es un conjunto finito y no vacío
de elementos llamados vértices y U es el conjunto cuyos elementos se componen de
subconjuntos de X de cardinalidad dos (2), llamados aristas.

Grafo orientado: Un grafo G* es orientado, cuando sus aristas tienen asignadas
direcciones, o sea cuando existe una relación de precedencia entre los elementos.
Sus puntos se llaman nodos, y sus líneas arcos. En estos casos U es una familia de
pares ordenados resultantes del producto cartesiano de X.

HISTORIA

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg".
Un río con dos islas atraviesa laciudad. Las islas estan unidas, entre si y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar.

Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo, el primer grafo, diseñado para resolver un problema.

Mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados.

A partir de Euler el modelado mediante grafos fue desarrollando esta metodología hasta convertirse en la actualidad, en una herrramienta de trabajo para ciencias tan diferentes como la Física, la Química, la Sicosociología, la Economía, la Lingüística, etc. La teoría de grafos está íntimamente relacionada con varias ramas de la Matemáticas como por ejemplo la Teoría de Conjuntos, el Análisis Numérico, Probabilidad, Topología, etc. y es la base conceptual en el tratamiento de problemas
combinatorios.

La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara representación de cualquier relación (de orden, precendencia, etc) lo que facilita enormemente tanto la fase de modelado como de resolución del problema. Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión .

Una aplicación frecuente de la teoría de grafos es la del método de camino hamiltoniano óptimo para decidir el camino a seguir por un cobrador, de tal modo de economizar sus energías, las suelas de sus zapatos y su bolsillo.

El objetivo es hallar un camino que pase por todos las casas una y solo una vez y que
nos de el costo menor en distancia. Dicho de otro modo, se deben buscar las
permutaciones de las casas de forma tal que la distancia recorrida total sea mínima.
Se conoce la distancia entre cada par de casas, según si las calles son flechadas o no
se orientarán o no las conexiones entre pares de casas.

Obsérvese que si se hicieran todas las permutaciones, suponiendo un caso muy reducido de diez casas, se tendrían más de 3 millones de permutaciones (10!).
Si cada casa es representada por un vértice y cada camino entre par de casas por una arista ponderada por la distancia mínima entre pares de casas, tendremos un grafo completo y simétrico
(cuando no hay calles flechadas).

El problema se reduce entonces, a obtener un camino hamiltoniano óptimo. Todo
algoritmo conocido para encontrar ciclos hamiltonianos requiere al menos un tiempo
exponencial de cálculo, o factorial en el peor de los casos.

Otro ejemplo para el que grafos provee un natural modelo matemático :
Supongamos que el siguiente grafo representa una red de líneas de teléfonos (o de
comunicaciones). Estamos interesados en la vulnerabilidad respecto a interrupciones
accidentales.

GRADO 

 Grado de x, es la suma del semigrado exterior e interior de x. O sea, es el número de arcos con una extremidad en x.
d(x) = d+(x) + d-(x)
Si todos los vértices tienen el mismo grado, el grafo al que pertenecen se llama grafo
regular.

Recorrido de grafos.
Cadena (concepto no orientado): Es una secuencia de aristas de G, tal que cada arista de la secuencia tiene un extremo común con el arco precedente y otra con el siguiente.

Largo de una cadena, es el número de aristas de la secuencia.

Cadena elemental, es aquella que no repite vértices.

Cadena simple, es aquella que no repite aristas.

Camino (concepto orientado) Es una cadena m = {u1, u2,..., uq} en la que para todo ui (con i < q) el
extremo terminal de ui coincide con el extremo inicial de ui+1.

Las definiciones de largo de un camino, camino elemental y camino simple son análogas a las de cadenas, con la salvedad de la orientación.

CIRCUITO,  es un camino elemental (que no repite nodos).

TRAYECTORIA , es un camino cuyos arcos se pueden recorrer en su sentido directo o contrario.

Ciclo Euleriano es aquel que incluye todas las aristas del grafo una sola vez, conteniendo cada vértice por lo menos una vez.

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple)
tocando todos los vértices del grafo.

Todo multigrafo que posee un ciclo Euleriano es conexo y todos sus vértices tienen grado par .

A partir del siguiente ejemplo daremos una idea del mecanismo utilizado por Euler para demostrar que la conexidad y el grado par de todos los vértices de un multigrafo, son condiciones necesarias y suficientes para garantizar la existencia de un ciclo Euleriano. Tenemos este grafo que es conexo y sus vértices tienen grado par. 

1) Primero se comienza por trazar un camino simple desde un vértice, p. ej a. Supongamos que recorremos a-d-j-n-o-k-l-h-f-e-b-a. Volvimos a a. La propiedad del grado par, significa que siempre podemos abandonar cada vértice al que entramos, exepto a. Es decir que cualquier cadena que trazemos desde a debe volver a a, formando un ciclo.

2) Las restantes aristas del grafoinicial , conforman un grafo no conexo, pero todos sus vértices
mantienen el grado par, ya que al retirar el ciclo encontrado, se redujo cada grado
 en una cantidad par .

Cada subgrafo conexo posee un ciclo Euleriano: d-c-i-j-k-e-d y h-g-m-h.

3) Estos dos ciclos pueden ser insertados en el ciclo encontrado en 2) en los vértices
comunes d y h respectivamente, originando un ciclo Euleriano a-d-c-i-j-k-e-d-j-n-o-kl-
h-g-m-h-f-e-b-a, en el grafo original.

Teorema E.1: Un multigrafo (no orientado) G = (X,U) posee un ciclo Euleriano sii
G es conexo y todos sus vértices son de grado par.
Una Cadena Euleriana es una cadena que recorre todas las aristas del grafo una sola
vez incluyendo todos los vértices.