Teoria de grafos

Unidad VI. Teoría de grafos.

1. Elementos y características de los grafos.

2. Representación de los grafos.

3. Algoritmos de recorrido y búsqueda.

4. Aplicaciones de grafos.

5. Arboles.

6. Redes.

1.- INTRODUCCIÓN.
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 problemasinfluyeron 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 serepresentan 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 deellos.
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 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 vértices en forma depolí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éctrica, unalcantarillado 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, como el siguiente:

En este grafo se ha autorizado una arista que tienesus 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 o dos aristas orientadas.
Aquí 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 vértices: es una fuente. Del vértice e sólo entran vértices: es unagujero, 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 todas 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 querepresenta 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 unciclo 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 vértices, los arboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles. Los árboles son grafos que conectan vértices utilizando el menor número...