← Volver a los ejercicios

Excentricidad, radio, diámetro y centro

La excentricidad de un vértice es la mayor de sus distancias al resto, y una búsqueda en amplitud desde ese vértice las calcula todas. Con las excentricidades de los ocho vértices ya salen el radio, el diámetro y el centro. Aquí se corre la amplitud, se llenan las excentricidades y se cierran las tres cifras.

1. El grafo y la fuente

En ámbar, la fuente. En azul claro, el vértice que acaba de salir de la cola. Encima de cada vértice, su distancia a la fuente cuando ya la tiene.

2. La amplitud desde esa fuente

Paso 0 de 0
La cola

3. La excentricidad de cada vértice

Una amplitud por vértice y la mayor de sus distancias. Se puede responder corriendo la traza de arriba con cada fuente.

Excentricidad de p
Excentricidad de q
Excentricidad de r
Excentricidad de s
Excentricidad de t
Excentricidad de u
Excentricidad de v
Excentricidad de w

4. Radio, diámetro y centro

Radio: la menor de las excentricidades
Diámetro: la mayor de las excentricidades
El centro: marque los vértices cuya excentricidad es igual al radio.

5. Un grafo que no es conexo

Al correr amplitud(p), ¿cuántos vértices se quedan en −1?

¿Qué devuelve excentricidad(p) en este grafo?

6. Para llevarse

Sin solución aquí. En el grafo con ciclos, corra la amplitud desde los dos vértices del centro y diga qué tienen en común sus arreglos de distancias. En el árbol, compruebe que el diámetro es exactamente el doble del radio y encuentre un árbol de ocho vértices donde no lo sea. Después escriba qué habría que cambiarle a excentricidad para que avise cuando el grafo no es conexo, sin agregar un recorrido más.