Quiero saber cómo calcular la excentricidad de un vértice en
a ponderado grafo, se que cuando hablamos de grafo ponderado si queremos
para calcular cualquier distancia consideramos los pesos en lugar del número de aristas, pero en el caso de la excentricidad todos los artículos que encontré sobre la
internet nunca mencionó el caso del grafo ponderado.
Respuesta
¿Demasiados anuncios?
La definición habitual de excentricidad de un vértice $v$ en un no ponderado gráfico $G$ es la distancia máxima entre $v$ a los vértices $w\in G$ . Se puede utilizar literalmente exactamente la misma definición para un grafo ponderado.
Más explícitamente, para un grafo ponderado no dirigido conectado $G=(V,E,w)$ donde $w:E\to \mathbb R^{\geq 0}$ es una función de peso, define la distancia entre vértices $v,w$ ser $$d_G(v,w)=\min_P \sum_{e\in P}w(e) $$ donde el mínimo es sobre todos los caminos $P$ conectando $v$ y $w$ .
Definamos ahora la excentricidad de un vértice $v$ como $$e_G(v)=\max_w d_G(v,w).$$
No estoy seguro de lo extendido que está el uso de esta definición, pero parece una generalización bastante natural.
