Algebra

http://teoriadegrafos.metroblog.com/6_6_aplicaciones_de_grafos_y_arboles
Teoría de grafos
Este blog fue elaborado con la intención de dar a conocer información estructurada sobre la teoría de Grafos y sus elementos.
Jueves 15 de Diciembre de 2011
6.6 Aplicaciones de grafos y árboles.
¿Qué es un grafo? Recordemos que un grafo G es el par (V, A) que representa una relación entre un conjunto deVértices y otro de Aristas. Representaremos cada elemento arista como un par de elementos de V. Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. Las aplicaciones más importantes de los grafos son las siguientes: • Rutas entre ciudades. • Determinar tiempos máximosy mínimos en un proceso. • Flujo y control en un programa EJEMPLOS DE APLICACIONES DE GRÁFICAS. Los grafos son la representación natural de las redes, en las que estamos cada vez más incluidos.
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formadopor dos conjuntos: • Un conjunto V de puntos llamados vértices o nodos. • Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos. En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de unmultígrafo. Si los arcos se pueden recorrer en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo. A pesar de que un grafo parece una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo estudio ha dado lugar auna completa teoría matemática. Fue Leonhard Euler quien ideó los grafos como una manera muy potente y elegante de resolver el problema de los puentes de Königsberg. Königsberg (hoy Kaliningrado en Rusia) era en tiempos de Euler (siglo XVIII) una ciudad prusiana cruzada por siete puentes. Durante la época se suscitó la cuestión no resuelta de si era posible recorrer toda la ciudad cruzando cadauno de los puentes una y sólo una vez. Si hacemos una representación esquemática de la ciudad vemos que los puentes unen cuatro porciones de tierra. La búsqueda por prueba y error no conduce a ningún resultado. El problema de los puentes de Königsberg. Esta ciudad esta recorrida por el río Pregel que crea dos islas. ¿Se puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7puentes que unen la parte insular de la ciudad con el resto? La solución de Euler. El famoso matemático abstrajo los detalles de la forma de la ciudad y sus puentes para quedarse con la conectividad, dando lugar a una de los primeros grafos. El orden de todos los vértices es impar, lo que implica que es imposible recorrerlos pasando una sola vez por cada uno. Euler realizó una abstracción delproblema representando mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada dos puntos por cada puente. Llamó orden de cada vértice al numero de arcos que se reunían en el y se percató que el orden de cada vértice visitado en un recorrido sin saltos ha de ser par (sale un enlace y entra otro) excepto para dos puntos del grafo: aquellos donde se inicia y donde se acaba elrecorrido, que han de tener orden impar. Si el vértice donde se inicia y se acaba son el mismo entonces todos los vértices han de ser de orden par. En el problema de Königsberg el orden de todos los nodos es 3, esto es impar, por lo que quedó claro que no existía solución para el problema. No había un camino que recorriese todos los puentes pasando una sola vez por cada uno de ellos. El interés de...