Grafos

Estudiante: Martha Vanessa Alvarado López
Cédula: 0115570386
Centro Universitario: Desamparados-42

Ensayo: “Grafos”
“Para aquellos que preguntan cuál es la cantidad más infinitamente pequeña en las matemáticas, la respuesta es cero. Por lo tanto no hay tantos misterios ocultos en este concepto, ya que por lo general se cree que sí.” - Leonhard Euler.
Existen cierto tipo de problemasque ú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 se ocupa 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 siempremotivado 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 de Königsberg”.
A partir de tal fecha muchos matemáticos importantes han realizado contribuciones.
La teoría de grafos está estrechamente ligada a otros campos de la matemática como la topología (en realidad la teoría de grafos estopología mono dimensional), la teoría de grupos, la teoría de conjuntos y la combinatoria. Esta 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 algunas aplicaciones de la misma.
Los grafos pueden ser considerados formalmente como diagramas o dibujos (representacióndiagramática), o bien algebraicamente como un par de conjuntos y una aplicación entre esos conjuntos (representación algebraica).

Es importante comentar que un grafo contiene ú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,..)



Si queremos formalizar el concepto degrafo, 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, arcoso 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.

El número de vértices del grafo G, |V (G)|, se denomina orden del grafo. El númerode lados del grafo G, |E (G)|, se conoce como tamaño del grafo. Un grafo es finito si |V (G)| y |E (G)| son finitos. En el caso en que E (G) sea vacío diremos que el grafo es degenerado. En el caso que la aplicación de incidencia de un grafo sea inyectiva, es simple.

Un grafo es nulo si tiene todos sus vértices aislados, entendiendo por vértice aislado aquel que no es extremo de ningún lado.Un grafo es completo si posee un arco de extremos (u, v) para cada par de vértices u y v distintos. Un grafo es regular de grado n si el grado de todos sus vértices es n, siendo el grado de un vértice el número de lados del grafo tales que uno de sus extremos es ese vértice.

Los grafos son usados con frecuencia para representar redes de comunicación o transporte. En un grafo que represente unade las redes es importante conocer la existencia de caminos que recorran todas las aristas o todos los vértices. Para ellos comenzaré dando una serie de definiciones básicas.

Como ya comentaba en la introducción Euler fue el que planteando el problema en la teoría de grafos “resolvió” el problema de los 7 puentes Könisberg. El problema consistía en encontrar una ruta en la ciudad que...