Please enable JavaScript.

Coggle requires JavaScript to display documents.

Teoría de Grafos - Coggle Diagram

- - - - El algoritmo de Dijkstra: Resuelve las cortas de origen único problemas de ruta.
      - Algoritmo de Bellman-Ford: Resuelve el problema de una sola fuente, si borde pesos pueden ser negativos.
      - Un algoritmo de búsqueda *: Resuelve para el par de ruta más corta única utilizando la heurística para tratar de acelerar la búsqueda.
      - Algoritmo de Floyd-Warshall: Resuelve todos los pares caminos más cortos.
      - Algoritmo de Johnson: Resuelve todos los pares de trayectorias más cortas, y puede ser más rápido que Floyd-Warshall en grafos dispersos.
  - - - Ejemplo
      - Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino:
      - Clave: verde: inicio, el azul: objetivo, de color anaranjado: visitado.
      - Nota: En este ejemplo se utiliza una coma como separador decimal.
      - Ilustración de la búsqueda A * para la búsqueda de ruta desde un nodo de inicio a un nodo objetivo en un robot de planificación de movimientos problema.
      - Una búsqueda de * que utiliza una heurística que es de 5,0 (= ε) veces a la heurística consistente, y obtiene una ruta subóptima.
- - - - 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értice] contiene la información de la arista (1 - conectado, 0 - no conectado).
- - - - 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' oimpar' 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.
  - - - 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.
      - 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.
      - Grafos planos: Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se intersecta.
      - 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.