Autor Tema: 2 trayectorias máximas tienen almenos un vértice en común

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

21 Septiembre, 2022, 07:20 pm
Leído 116 veces

Hibridblood

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • País: mx
  • Karma: +0/-0
Auxilio
Cómo puedo demostrar que 2 trayectorias máximas dentro de un grado tamaño n, tienen al menos un vértice en común

22 Septiembre, 2022, 07:23 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,437
  • País: es
  • Karma: +0/-0
Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente

Cómo puedo demostrar que 2 trayectorias máximas dentro de un grado tamaño n, tienen al menos un vértice en común

 Para que el resultado sea cierto el grafo debe de ser conexo. En ese caso si tuvieses dos trayectorias máximas de longitud \( n \) disjuntas, tendrían que poder unirse por un camino. Es decir existe un camino de longitud al menos \( 1 \) que une dos vértices \( P \) y \( Q \) en cada una de las dos trayectorias.

 Ahora si a ese camino le añades las dos mitades de mayor longitud en cada trayectoria tienes un camino de longitud mayor o igual que:

\(  1+\dfrac{n}{2}+\dfrac{n}{2}=n+1 \)

 Esto contradice la maximalidad de las trayectorias originales.

Saludos.

24 Septiembre, 2022, 06:46 pm
Respuesta #2

Hibridblood

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • País: mx
  • Karma: +0/-0