Tipos de Grafos

Grafo simple. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. 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. Es aquel que acepta una sola 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.

Multigrafo o pseudografo: Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Todos sus vértices tienen el mismo grado de valencia.

Grafo orientado: grafo dirigido o dígrafo. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha. Aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Es aquel que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo dos regiones vecinas.

Grafo etiquetado: Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. Aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Podemos establecer que un grafo es plano gracias al Teorema de Kuratowski.

Grafo aleatorio: Grafo cuyas aristas están asociadas a una probabilidad. Todos sus vértices tienen el mismo grado de valencia. Grafo cuyas aristas están asociadas a una probabilidad.

Hipergrafo: Grafo cuyas aristas están asociadas a una probabilidad. Grafos con conjunto de vértices y aristas de cardinal infinito. 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.

Grafo infinito: Aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Grafos con conjunto de vértices y aristas de cardinal infinito. Todos sus vértices tienen el mismo grado de valencia.

Grafo plano: Aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Todos sus vértices tienen el mismo grado de valencia. Grafo cuyas aristas están asociadas a una probabilidad.

Grafo regular: Todos sus vértices tienen el mismo grado de valencia. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. 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.

Grafo dual: Aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. 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. Aquel que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo dos regiones vecinas.

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. Algoritmo de Prim. Búsqueda en anchura. Búsqueda en profundidad.

Es un algoritmo de búsqueda no informada utilizado para recorrer o buscar elementos en un grafo. Algoritmo del vecino más cercano. Algoritmo de Bellman-Ford. Búsqueda en anchura (BFS).

Es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Algoritmo de Dijkstra. Algoritmo de búsqueda en profundidad (DFS). Algoritmo de búsqueda en anchura (BFS).

El algoritmo encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo. Algoritmo de búsqueda A*. Algoritmo de búsqueda en anchura (BFS). Algoritmo del vecino más cercano.

Este método genera rápidamente un camino corto, pero generalmente no el ideal. Algoritmo de cálculo de los componentes fuertemente conexos de un grafo. Algoritmo de búsqueda A*. Algoritmo del vecino más próximo.

Es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. Algoritmo de Dijkstra. Algoritmo de Bellman-Ford. Ordenamiento topológico.

Genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). Ordenamiento topológico. Algoritmo de Bellman-Ford. Árbol recubridor mínimo.

Es una ordenación lineal de todos los nodos de G que satisface que si G contiene la arista dirigida uv entonces el nodo u aparece antes del nodo v. Ordenamiento topológico. Componente fuertemente conexo. Algoritmo del vecino más cercano.

Propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Algoritmo de Ford-Fulkerson. Algoritmo de Kruskal. Algoritmo de Bellman-Ford.

Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Algoritmo del vecino más cercano. Algoritmo de Kruskal. Algoritmo de Prim.

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. Algoritmo de Ford-Fulkerson. Algoritmo de Bellman-Ford. Algoritmo de Floyd-Warshall.