Autor Tema: Excentridad de vértices

0 Usuarios y 1 Visitante están viendo este tema.

07 Marzo, 2021, 06:51 pm
Leído 268 veces

carambola

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 49
  • País: es
  • Karma: +0/-0
Hola. Como se demostraría est0:

Si en un grafo conexo G, un vértcie $$v$$ tiene excentridad $$h$$, comprobad que la excentridad de los vecinos de $$v$$ es o bien $$h$$, o bien $$h+1$$, o bien $$h-1$$.

Muchas gracias

07 Marzo, 2021, 07:11 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 2,299
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La idea es que si \[ v' \] es vecino de \[ v \], \[ u \] es un vértice cualquiera y \[ d(v,u)=h \], entonces necesariamente \[ d(v',u) \] debe ser \[ h-1,h \] o \[ h+1 \].

En efecto, si fuera \[ d(v',u)<h-1 \], tendríamos un camino de \[ v \] a \[ u \] de longitud menor que \[ h \] (vamos de \[ v \] a \[ v' \] y luego de \[ v' \] a \[ u \] en menos de \[ h-1 \] pasos). El mismo argumento con \[ v,v' \] intercambiados muestra que no puede ser \[ d(v',u)>h+1 \].

Como la excentricidad de \[ v \] es \[ \max_u d(u,v) \] (con \[ u \] recorriendo todos los vértices del grafo), el resultado se sigue de la observación anterior.
La ecuación más bonita de las matemáticas: \( d^2=0 \)