Un gráfico ponderado es un tipo especial de gráfico en el que a los bordes se les asignan algunos pesos que representan el costo, la distancia y muchas otras unidades de medida relativas.
Ejemplo de un gráfico ponderado
Aplicaciones del gráfico ponderado:
- Juegos de arrays en 2D: En los juegos de arrays en 2D se pueden usar para encontrar la ruta óptima para la suma máxima a lo largo de los puntos de inicio a fin y se pueden encontrar muchas variaciones en línea.
- Árboles de expansión: los gráficos ponderados se utilizan para encontrar el árbol de expansión mínimo del gráfico que representa el costo mínimo para atravesar todos los Nodes en el gráfico.
- Gráficos de restricciones: los gráficos se utilizan a menudo para representar restricciones entre elementos. Se utiliza en programación, diseño de productos, asignación de activos, diseño de circuitos e inteligencia artificial.
- Gráficos de dependencia: los gráficos ponderados dirigidos se pueden usar para representar las dependencias o el orden de precedencia entre los elementos. Se asignará prioridad para proporcionar un flujo en el que resolveremos el problema o recorreremos el gráfico de mayor a menor prioridad. Dichos gráficos se usan a menudo en proyectos grandes para establecer qué componentes dependen de otros componentes y se usan para minimizar el tiempo total o el costo de finalización mientras se respetan las dependencias.
- Compiladores: los gráficos ponderados se usan mucho en los compiladores. Se pueden usar para la inferencia de tipos, para el llamado análisis de flujo de datos y muchos otros propósitos, como la optimización de consultas en lenguajes de bases de datos.
Aplicaciones en tiempo real del gráfico ponderado:
- Redes de transporte: al usar gráficos ponderados, podemos determinar cosas como la ruta que lleva menos tiempo o la ruta con la menor distancia total. Esta es una simplificación de cómo se pueden usar los gráficos ponderados para cosas más complejas como un sistema GPS. Los gráficos se utilizan para estudiar los patrones de tráfico, los tiempos de los semáforos y mucho más por parte de muchas grandes empresas tecnológicas como OLA, UBER, RAPIDO, etc. Las redes de gráficos se utilizan en muchos programas de mapas como Google Maps, Bing Maps, etc.
- Gráficos de enlaces de documentos: los gráficos ponderados de enlaces se utilizan para analizar la relevancia de las páginas web, las mejores fuentes de información y los buenos sitios de enlaces al contar el número de vistas como pesos en el gráfico.
- Epidemiología: se pueden usar gráficos ponderados para encontrar la distancia máxima de transmisión de una persona infecciosa a una sana.
- Gráficos en la teoría cuántica de campos: los vértices representan estados de un sistema cuántico y los bordes representan transiciones entre ellos. Los gráficos se pueden utilizar para analizar integrales de trayectoria y su suma genera una amplitud cuántica. La investigación para encontrar la frecuencia máxima a lo largo de una ruta se puede realizar utilizando gráficos ponderados.
- Gráficos de redes sociales: Podemos encontrar que todos los usuarios están conectados en una red tanto directamente (conexión directa) como indirectamente (conexión indirecta). Pero ahora los gráficos ponderados también se usan en las redes sociales para muchos propósitos, por ejemplo, en los últimos tiempos, Instagram está usando funciones como amigos cercanos, que no es lo mismo que todos los amigos. Estas funciones se implementan mediante gráficos ponderados.
- Gráficos de tráfico de paquetes de red : los gráficos de tráfico de paquetes de red se utilizan para analizar la seguridad de la red, estudiar la propagación de gusanos y rastrear actividades delictivas o no delictivas.
Ventajas del gráfico ponderado:
- Se puede usar para representar redes sociales complejas, placas de circuitos y muchos más tipos de aplicaciones complejas de la vida real que no pueden implementarse con ninguna otra estructura de datos.
- Se puede utilizar para encontrar el camino más corto entre dos Nodes cualesquiera.
- El concepto de árbol de expansión ayuda a los usuarios a encontrar una ruta que visite todos los Nodes del gráfico con un costo mínimo.
Desventajas del gráfico ponderado:
- Se necesita más cantidad de memoria que un gráfico normal.
- Como principiante, los gráficos ponderados pueden ser muy complejos de entender para los usuarios.