Zusammenfassung der Ressource
GRAFOS
- APLICACIONES
- Redes Sociales
Anmerkungen:
- Los nodos son los usuarios, y las aristas representan relaciones de amistad o
conexión
- Algoritmos de Búsqueda
Anmerkungen:
- Como el algoritmo de búsqueda en anchura (BFS) y el algoritmo de
búsqueda en profundidad (DFS), que recorren grafos para encontrar
rutas o analizar componentes.
- Optimización de Rutas
Anmerkungen:
- Con algoritmos como Dijkstra o Floyd-Warshall, utilizados para
encontrar caminos más cortos en un grafo ponderado.
- Flujo de Datos y Redes
Anmerkungen:
- Usado en modelado de redes de flujo, Internet, redes eléctricas, etc.
- ALGORITMOS COMUNES
- DFS
Anmerkungen:
- Recorre
un grafo adentrándose lo más profundo posible antes de retroceder.
- BFS
Anmerkungen:
- Recorre un grafo nivel por nivel, explorando todos los nodos vecinos antes
de profundizar.
- Dijkstra
Anmerkungen:
- Encuentra
el camino más corto desde un nodo origen hasta todos los demás en un grafo
ponderado.
- Kruskal y Prim
Anmerkungen:
- Algoritmos
para encontrar el árbol de expansión mínima en grafos ponderados.
- REPRESENTACIONES
- Matriz de Adyacencia
Anmerkungen:
- Una matriz cuadrada donde el valor en la posición (i, j) indica si hay una
arista entre los nodos i y j. Para grafos ponderados, el valor de la
posición puede ser el peso de la arista.
- Lista de Adyacencia
Anmerkungen:
- Un arreglo o lista en el que cada elemento contiene los nodos adyacentes a un
nodo determinado. Es una representación eficiente en espacio para grafos
dispersos.
- TIPOS
- Grafos Dirigidos
Anmerkungen:
- Cada arista tiene una dirección asociada. Esto significa que la relación entre dos
vértices es unidireccional, y se representa mediante una flecha que indica la
dirección de la conexión.
- Grafos No Dirigidos
Anmerkungen:
- Las aristas no tienen dirección. Esto significa que la relación entre dos vértices
es bidireccional y simétrica.
- Grafo Ponderado
Anmerkungen:
- Las aristas tienen un peso asociado, que puede representar distancia, costo u otra
magnitud relevante.
- COMPONENTES
- Vértice
Anmerkungen:
- Los
vértices son los puntos fundamentales en un grafo y representan
entidades individuales. Pueden representar cualquier cosa, desde
ubicaciones en un mapa hasta elementos en un conjunto de datos.
- Arista
Anmerkungen:
- Son las conexiones entre los vértices y pueden tener direcciones o no, dependiendo
de si el grafo es dirigido o no dirigido.
- CONCEPTO
Anmerkungen:
- Es un conjunto de elementos llamados vértices (también conocidos como nodos) y un
conjunto de conexiones entre pares de vértices, llamadas aristas.