Centro y mediana de un grafo
Si en el grafo anterior, las aristas representan calles y los vértices intersecciones.
¿Dónde colocar un puesto de policía? ¿Y un quiosco?
El puesto de policía debería (p.e.) estar en el vértice que
minimice el tiempo de respuesta entre la estación y el posible punto de acción.
Es decir, minimizar la distancia mas larga.
El quiosco debería (p.e.) minimizar el promedio de las distancias al puesto.
Se define la excentricidad de un vértice v en un grafo como la distancia de v
al vértice mas lejano.
Se define el radio de un grafo como el mínimo de las excentricidades de los
vértices del grafo.
Se define el diámetro de un grafo como el máximo de las excentricidades del grafo.
Se define el centro del grafo como el subgrafo inducido por los vértices con
excentricidad igual al radio.
Se define la distancia de un vértice v en un grafo como la suma de las distancias de v
a cada vértice de G.
Se define la mediana como el subgrafo inducido por los vértices que tienen
mínima distancia
v2 e=6
e=6 v1
v4 e=3
e=5 v3
v5 e=5
e=4 v6
v8 e=4
v7 e=3
v9 e=3
Distancias:
V1: 1 2 3 3 3 4 5 6->27
V2->27
V4->15
V3: 1 1 2 2 2 3 4 5->20
V5->20
V7->15
V6: 2 1 1 1 1 2 3 4->15
V6->15
Radio
Diámetro
Centro
Mediana
3
6
Policía
<v4 v7 v9>
<v4 v6 v7 v8> Quiosco
V8->15
V9->16
Descargar

Diapositiva 1