GRAFOS

GRAFOS

TIPO DE ESTRUCTURA
1. La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos. Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas).
2. - Grafo simple. o simplemente grafo es aquel que acepta una sola una 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.
3. - Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
4. - Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha
5. - Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.
6. - Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.
7. - Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
8. - Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.
TERMINOLOGÌA
1. Vèrtice: Nodo.
  1. Enlace: Conexión entre dos nodos.
    1. Adyacencia: Se dice que dos nodos son adyacentes si entre ellos hay un enlace directo.
      1. Vecindad: Conjunto de nodos adyacentes a otro.
        Camino: Conjunto de nodos que hay que recorrer para llegar desde un nodo origen hasta un nodo destino.
        Grafo Conectado: Aquél que tiene camino directo entre todos los nodos.
        Grafo Dirigido: Aquél cuyos enlaces son unidireccionales e indican hacia donde están dirigidos.
        Grafos con Pesos: Aquél cuyos enlaces tienen asociado un valor. En general en este tipo de grafos no suele tener sentido que un nodo se apunte a sí mismo porque el coste de este enlace sería nulo.
UTILIDAD
1. Los Grafos son una especie de dibujos que sirven para dar soluciones óptimas a diversos problemas, ya sea de transporte, servicio de red o cualquier problema en el cual se desee conocer la vía más económica para resolverlo.
IMPLEMENTACIÒN
1. Arreglos-Matrz de Adyacencia
  1. Para un grafo con |V| ∣V∣vertical bar, V, vertical bar vértices, una matriz de adyacencia es una matriz de |V| \times |V| ∣V∣×∣V∣vertical bar, V, vertical bar, times, vertical bar, V, vertical bar de ceros y unos, donde la entrada en el renglón i ii y la columna j jj es 1 si y solo si la arista (i, j) (i,j)left parenthesis, i, comma, j, right parenthesis está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón i ii, columna j jj y reserva un valor especial (tal vez null) para indicar una arista ausente. Aquí está la matriz de adyacencia para el grafo de la red social.
    1. En JavaScript, representamos esta matriz como: [ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 1, 1, 1, 0, 1, 0, 0, 0, 1], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
2. Lista de Adyacencia
  1. Representar un grafo con listas de adyacencia combina las matrices de adyacencia con las listas de aristas. Para cada vértice i ii, almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de |V| ∣V∣vertical bar, V, vertical bar listas de adyacencia, una lista de adyacencia por vértice. Aquí está una representación de una lista de adyacencia del grafo de la red social.
    1. En JavaScript, representamos estas listas de adyacencia como: [ [1, 6, 8], [0, 4, 6, 9], [4, 6], [4, 5, 8], [1, 2, 3, 5, 9], [3, 4], [0, 1, 2], [8, 9], [0, 3, 7], [1, 4, 7] ]
RECORRIDOS
1. Lo que queremos conseguir es pasar por todos los nodos de un grafo evitando tratarlos dos veces (por ejemplo, si se están escribiendo en pantalla el contenido de todos los nodos del grafo hay que evitar que un nodo se escriba dos veces). Hay dos tipos de recorrido de un grafo:
  1. En profundidad
    1. Recorrido en profundidad: En este tipo de recorrido hay que usar una pila para ir almacenando los nodos que nos falta visitar. Vamos a ver como se comportaría este algoritmo si queremos recorrer el grafo anterior partiendo de “A”:
  2. A lo ancho
    1. Recorrido a lo ancho: La implementación de este recorrido es exactamente igual que la del recorrido en profundidad, con la única diferencia de que en lugar de una pila, usamos una cola. Veamos como se comportaría este algoritmo si queremos recorrer el grafo anterior partiendo de “A”:
ALGORITMO
1. Dijkstra
  1. El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
2. Prim
  1. El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo. El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
3. Floyd-Warshall
  1. el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica. Muchos problemas de la vida cotidiana se pueden expresar e incluso resolver en forma de grafo. Existen algoritmos que encuentran distintos tipos de soluciones, tanto booleanas como de eficiencia. El grafo se representa en una tabla (matriz) que se conoce como “matriz de adyacencia” y representa si existe una unión entre dos nodos (boolean).
4. Kruskal
  1. El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956. 1 2 Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo es el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka.
JUAN CAMILO ALMANZA OROZCO - PEDRO JOSE MEDINA MORENO

Next up

Description

Resource summary

Media attachments

0 comments

Similar

	Created by TheKing alma over 7 years ago