Teoría De La Computación.: Teoría de grafos

Teoría de Grafos.

Leonard Euler, uno de los grandes matem aticos de la historia, viv a en Konigsberg (actual Kaliningrado), cuya ciudad es dividida en varias regiones por el r o Pregel.
Los colegas de Euler se divert an discutiendo un problema: c omo hacer una caminata por la ciudad cruzando cada uno de sus siete puentes una y s olo una vez, y volver al punto
de partida. Un plano de la ciudad mostraba algo como se ve en la figura.
A la figura la llam o grafo, a los puntos los llam o v ertices y a las l neas las denomin o aristas. Estudi o si una gura lineal se pod a dibujar con un solo trazo, sin levanta el l apiz del papel y sin pasar dos veces por el mismo sitio. Y as , estudiando v ertice (o nodos), conectados a trav es de aristas, naci o lo que hoy conocemos como la teorí a de grafos. Esta teor a, juega un papel importante en la fundamentaci on matem atica de las Ciencias de la Computaci on. Los grafos constituyen una herramienta b asica para modelar fen omenos discretos (de los cu ales nos ocuparemos en el siguiente cap tulo) y son fundamentales para la comprensi on de las estructuras de datos y el an alisis de

algoritmos.El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Konigs-berg es considerado como el primer resultado de la teor a de grafos. Tambi en se considera uno de los primeros resultados topol ogicos en geometr a (que no depende de ninguna medida). Este ejemplo ilustra la profunda relaci on entre la teor a de grafos y la topologí a.
En 1845 Gustav Kirchho public o sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos el ectricos (en realidad un circuito es un grafo). En 1852 Francis Guthrie plante o 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 es por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teor a de grafos formalmente. Ya que, tratar de resolverlo, los matem áticos t erminos y conceptos te oricos fundamentales de los grafos.

Definiciones:

Un grafo es un conjunto de vértices V con un conjunto de aristas E, de tal manera que cada arista se asocia a un par de vértices.

Grafo de 6 vértices y 7 arístas.

Si (x,y) es una arista de el grafo, al vértice "x" le llamaremos vértice de entrada o inicial y al vértice "y" le llamamos vértice de salida o terminal.

Denotamos por v(G) el numero de vértice y e(V) el numero de aristas.

Puesto que E es un conjunto de pares ordenados, es posible que existan pares repetidos en este caso el grafo tiene lados múltiplos.

También es posible que algún par ordenado de E tenga el mismo vértice de entrada y de salida. En este caso le llamaremos lazo o bucle.

Tipos de grafos

Grafo simple. o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.
Multigrafo o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos . Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha
Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (numero generalmente) o un etiquetado a los vértices.
Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.