El atributo que representan los pesos de los bordes depende del problema que el gráfico se utiliza para modelar .
Considere el mapa de un estado como un gráfico con las ciudades que forman los vértices y los bordes que indican la ruta de viaje de una ciudad a otra. Los pesos pueden denotar cualquiera de los siguientes.
- ¿Existe un libro que enseñe algoritmos, estructuras de datos y otros conceptos básicos de informática de una manera divertida?
- ¿Cuál es la diferencia entre consultas DNS iterativas y recursivas?
- ¿Por qué necesitamos el algoritmo de derivación de porter en Python?
- Cómo aprender a analizar algoritmos
- ¿Cuáles son los problemas de programación que resolvió que le hicieron decir "¡Guau! ¡Lógica asombrosa"?
- El costo asociado para viajar de una ciudad a otra.
- El tiempo que toma el viaje de una ciudad a otra.
El siguiente ejemplo es de Wikipedia
Considere la situación en la que una compañía de telecomunicaciones está tratando de tender el cable en un nuevo vecindario. Si se limita a enterrar el cable solo a lo largo de ciertos caminos (por ejemplo, carreteras), entonces habría un gráfico que contiene los puntos (por ejemplo, casas) conectados por esos caminos.
Algunos de los caminos pueden ser más caros porque son más largos o requieren que el cable esté enterrado más profundo; estos caminos estarían representados por aristas con pesos mayores. La moneda es una unidad aceptable para el peso del borde: no es necesario que las longitudes del borde obedezcan las reglas normales de la geometría, como la desigualdad del triángulo.
El escenario anterior se usa para explicar la idea detrás de un árbol de expansión mínima: Wikipedia, un modelo popular en la teoría de gráficos.
Referencias
- Árbol de expansión mínima – Wikipedia
- Gráfico de árbol de expansión mínima – GeeksforGeeks
Espero que haya ayudado.
