5. TEORIA DE GRAFOS

5. TEORIA DE GRAFOS

1. La teoría de grafos es un tema muy antiguo; sin embargo, es utilizado en muchas aplicaciones modernas. Sus ideas básicas fueron introducidas en el siglo XVIII por el matemático suizo Leonhard Euler. Los grafos son usados para resolver problemas en muchos campos, por ejemplo, se puede utilizar para diferenciar dos compuestos químicos con la misma fórmula molecular pero empleando distintas estructuras; para el caso de nuestra área de interés, un ejemplo es que los grafos pueden ser utilizados para establecer si dos computadoras están conectadas por un enlace de comunicaciones entre las de redes de computadoras.

   • 5.1 Elementos, características y componentes de los grafos.
     • Un grafo, G es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.
       • COMPONENTES
         • Aristas. Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos. Estas a su vez pueden ser: Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. Cruce: Son dos aristas que cruzan en un punto.
         • Vértices. Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. Estos a su vez pueden ser: Vértices Adyacentes: Si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente. Vértice Aislado: Es un vértice de grado cero. Vértice Terminal: Es un vértice de grado 1.
       • 5.1.1 TIPOS DE GRAFOS.
         • Grafo simple: Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n.
           • Grafo completo: Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices.
             • Grafo bipartido: Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2.
               • Grafo bipartido completo: Un grafo es bipartido completo si V=V1?V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr, donde V1 tiene r vértices y V2 tiene s vértices.
                 • Grafos planos: Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se intersecta.
                   • Grafos conexos: Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde "a" hacia "b".
                     • Grafo ponderado: Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.
   • 5.2 Representación de los grafos.
     • Representación por incidencia.
       • Lista de incidencia: El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista. Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).
     • Representación por adyacencia.
       • Listas de adyacencia: El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante. Matriz de adyacencia: Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V2)).
     • 5.2.1 REPRESENTACIÓN MATEMÁTICA.
       • En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de las gráficas estudia las propiedades de los grafos (también llamados gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
     • 5.2.2 REPRESENTACIÓN COMPUTACIONAL.
       • Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
         • Estructura de lista: Lista de incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. Lista de adyacencia: Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. Lista de grados: También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo. Estructuras matriciales: Matriz de adyacencia: El grafo está representado por una matriz cuadrada M de tamaño, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1, de lo contrario, es 0. Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértic
   • 5.3 Algoritmos de recorrido y búsqueda.
     • En ciencias de la computación, A* es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International ) describieron por primera vez el algoritmo en 1968.Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959 .A* consigue un mejor rendimiento tiempo usando heurística.
     • 5.3.2 A LO ANCHO.
       • En ciencias de la computación, A * (pronunciado “Una estrella”) es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968. Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959. A * consigue un mejor rendimiento tiempo usando heurística.
       • 5.3.3 EN PROFUNDIDAD.
         • En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo. Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud. Una pila (a menudo del programa pila de llamadas a través de recursión) se usa generalmente cuando la ejecución del algoritmo. El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual. El algoritmo entonces retrocede a lo largo de los nodos visitados anteriormente, hasta que enc

Images and files in the map