Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS (Conceptos (conexo (si para cualquier par de vértices existe al…
GRAFOS
Conceptos
- si para cualquier par de vértices existe al menos una trayectoria
Fuertemente conexo
- grafo dirigido para que cualquiera dos vertices existe camino dirigido de ida y regreso
- si tiene camino cerrado en el que no se repite ningùn vertice a excepción del primero que es a la vez final
- grafo simple no dirigido que satisface:
- G es conexo y no tiene ciclos
- sus aristas tienen sentido definido
- Aquel en que cada vertice tiene el mismo grado
- grafo simple en el que cada par de vertices está conectado por una arista (es como una malla)
- no existen múltiples aristas entre cada par de nodos.
- es lo opuesto a multigrafo
- existen múltiples aristas entre cada par de nodos
- es lo opuesto a simple
- cada arista tiene asociado un valor para indicar su peso
-
- encuentra árbol recubridor mínimo.
- 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
- genera el camino más corto en un grafo dirigido ponderado
- Determina camino mas corto entre vértices
- también llamado de algoritmo de caminos mínimos
- encuentra árbol recubridor mínimo
- Prim inicializa con un node, Kruskal con un borde
- Prim solo funciona en grafos conectados, Kruskal no es necesario
- Prim complejidad O(v2), Kruska O(logV)
Características
- Conexo
- sin ciclos
- se añade alguna arista se forma un ciclo
- es conexo y si se le quita alguna arista deja de ser conexo