Introducción a los Grafos Ponderados#
¿Qué son los grafos ponderados?
Los grafos ponderados son aquellos en los que se asigna un número (peso) a cada una de sus aristas. Estos pesos pueden representar distintas magnitudes como distancia, tiempo, costo o capacidad.
¿Para qué se utilizan los grafos ponderados?
Los grafos ponderados se usan en múltiples contextos, por ejemplo:
Redes informáticas, donde los pesos representan los costes de comunicación, los tiempos de respuesta o la distancia entre equipos.
Sistemas de transporte, como los vuelos de una línea aérea, donde los pesos pueden representar costos, tiempos de vuelo o distancias.
Definición formal de un grafo simple ponderado#
Un grafo ponderado es aquel en el que cada arista tiene asociado un número real llamado peso. Se dice que \(G\) es un grafo ponderado si tiene asociada una función
\[ W : E \rightarrow \mathbb{R} \]llamada función de ponderación.
La imagen de cada arista determinada por los vértices \(v_i\) y \(v_j\) se llama peso de la arista y se denota por \(W_{ij}\).
Sea \(G = (V, E)\) un grafo ponderado finito tal que
\[ V = \{v_1, \dots, v_n\} \]Se denomina matriz de pesos del grafo \(G\) a la matriz \(n \times n\)
\[ W = [a_{ij}] \]tal que
\[\begin{split} a_{ij} = \begin{cases} w_{ij}, & \text{si } \{v_i, v_j\} \in E, \\ \infty, & \text{en caso contrario.} \end{cases} \end{split}\]Es decir, se coloca el valor del peso cuando exista, y el símbolo \(\infty\) cuando no exista tal arista.
¿Cuál es uno de los problemas más frecuentes en los grafos ponderados?
Uno de los problemas más comunes consiste en determinar un camino de longitud mínima entre dos vértices de una red.
La longitud de un camino en un grafo ponderado se define como la suma de los pesos de las aristas que lo componen.
¿Qué puede representar el camino más corto en ejemplos reales?
El camino más corto puede representar distintas medidas según el contexto:
La distancia más corta en kilómetros o millas entre dos ciudades.
El menor tiempo de viaje entre una ciudad y otra.
El menor costo de transporte o conexión entre nodos o ciudades.