teoria de los grafos



JUAN LOAIZA


MATEMATICAS COMPUTACIONALES



PROFESOR ARMANDO



TEORIA DE GRAFOS



15 DE ABRIL 2013


Objetivo: Investigar y conocer a fondo lo referente a la teoría de grafos
Existen cierto tipo de problemas que únicamente tienen que ver con un determinado número de puntos y ciertos trazos que los unen. La Teoría de Grafos es la rama de la Matemática discreta que seocupa de tal tipo de problemas. La conectividad entre los elementos de un conjunto es pues el objetivo fundamental de la teoría de grafos.

La teoría de grafos es una de las áreas de la Matemática cuyo desarrollo ha estado siempre motivado por sus aplicaciones. Así, el primer artículo conocido sobre la misma fue escrito por Euler en 1736 para dar solución al célebre problema de “los puentes deKönigsberg”. La situación era la siguiente: ¿es posible encontrar una ruta en la ciudad que recorra los siete puentes, cruzando cada uno de ellos una sola vez y regresando al punto de partida?.














Euler demostró que no era posible.

A partir de tal fecha muchos matemáticos importantes han realizado contribuciones.

La teoría de grafos está estrechamente ligada a otroscampos de la matemática como la topología (en realidad la teoría de grafos es topología monodimensional), la teoría de grupos, la teoría de conjuntos y la combinatoria.

Como veremos mas adelante la teoría de grafos tiene aplicaciones en multitud de disciplinas, no restringiéndose solamente a las matemáticas.

A continuación expondremos los conceptos fundamentales de la teoría y algunasaplicaciones de la misma.

EL CONCEPTO DE GRAFO

Los grafos pueden ser considerados formalmente como diagramas o dibujos (representación diagramática), o bien algebraicamente como un par de conjuntos y una aplicación entre esos conjuntos (representación algebraica). También podemos considerar una tercera representación: la representación matricial.

A.- Definición geométrica.

Geométricamente, ungrafo G es un conjunto de puntos en el espacio, algunos de los cuales están unidos entre sí mediante líneas. Así por ejemplo la figura siguiente es un grafo.












Este grafo puede representar una multitud de situaciones posibles de la vida real. Podría simbolizar un mapa de carreteras, un circuito electrónico, una molécula química, etc.

Es importante comentar que un grafocontiene únicamente información topológica, es decir, información sobre las conectividades entre puntos, careciendo de información geométrica en el sentido euclideo (distancias, ángulos,..) Así, los dibujos siguientes representan el mismo grafo:








Definición algebraica

Si queremos formalizar el concepto de grafo, debemos recurrir al álgebra. Así un grafo G es una tripleta(E(G),V(G),F), donde E(G), y V(G) son conjuntos arbitrarios (V(G) siempre es no vacío) y F es una aplicación que a cada elemento de
E(G) le hace corresponder un par no ordenado de elementos (repetidos o no) de V(G).

A los elementos de V(G) se les conoce como vértices o nodos, y los de E(G) como lados, líneas, arcos o aristas. A F se le llama aplicación de incidencia. En el caso de que F(l)=(i, j),diremos i y j son los extremos de l.

Si dos vértices i, j están unidos por una misma arista diremos que son adyacentes. Por otra parte diremos que dos lados son adyacentes si tienen algún vértice en común.

Diremos que l0E(G) es un lazo cuando empieza y acaba en el mismo vértice, es decir cuando sea de la forma F(l)=(i,i) para algún vértice i de G.

Para poder representar algebraicamente ungrafo vamos a denotar a los lados por lj y a los vértices por vi.

Así, el grafo anterior














se puede expresar algebraicamente de la siguiente manera: G=(V(G),E(G),F)

V(G)={v1,v2,v3,v4}

E(G)={l1, l2, l3}

F definida por F(l1)=(v1,v2), F(l2)=(v2,v3), F(l3)=(v2,v4) o lo que es lo mismo F(l1)=(v2,v1), F(l2)=(v3,v2), F(l3)=(v4,v2) ya que como comentaba antes no...