15 Grafos ponderados

Notaciones:

$(G,W)$	grafo ponderado con $W:E(G)\longrightarrow \bbbr^+$
$w(G)$	peso de grafo $G$, $w(G)=\sum_{e\in G}w(e)$
$w(P)$	peso de camino $P$, $w(P)=\sum{e\in P}w(e)$
$d(v,w)$	distancia entre dos vértices, $d(v,w)=\min_P \{w(vPw)\}$
$dt(v)=\sum_w d(v,w)$	distancia total de un vértice

si $w(e)=1 \forall e\in E$ se reproduce la distancia de arriba

Notaciones:

$e(v)$	excentricidad, $e(v)=\max_{w\in G} \{d(v,w)\}$
${\mathrm{rad}}(G)$	radio del grafo $G$, ${\mathrm{rad}}(G)=\min_{v\in G}\{e(v)\}$
${\mathrm{diam}}(G)$	diámetro del grafo $G$, ${\mathrm{diam}}(G)=\max_{v\in G}\{e(v)\}$

Vocabulario:

centro	el centro del grafo $G$ es el subgrafo de $G$ inducido
	por los vértices con excentricidad mínima
mediana	la mediana del grafo $G$ es el subgrafo de $G$ inducido
	por los vértices con distancia total mínima

Teorema:

$G$ conexo $\qquad\Longrightarrow\qquad$ ${\mathrm{rad}}(G)\leq{\mathrm{diam}}(G)\leq 2\cdot {\mathrm{rad}}(G)$

Teorema:

Todo grafo es centro de un grafo.

Teorema:

El centro de un árbol consiste en uno o dos vértices.

¿Algoritmo que calcule el centro de un árbol?