Autor Tema: Numero de componentes de G

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

18 Noviembre, 2019, 05:30 am
Leído 882 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Sea \( G \) el grafo cuyo conjunto de vertices es \( \{1,2,3,...,15\} \) en donde \( i \) y \( j \) son adyacentes si su maximo comun divisor es estrictamente mayor que \( 1. \) Determine el numero de componentes de \( G \) y el largo del camino de largo maximo en \( G. \)
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 10:31 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Sea \( G \) el grafo cuyo conjunto de vertices es \( \{1,2,3,...,15\} \) en donde \( i \) y \( j \) son adyacentes si su maximo comun divisor es estrictamente mayor que \( 1. \) Determine el numero de componentes de \( G \) y el largo del camino de largo maximo en \( G. \)

Nota que:

\( 2,4,6,8,10,12,14 \) son todos adyacentes entre si, porque tienen al \( 2 \) como m.c.d
\( 3,6,9,12,15 \) son todos adyacentes entre si, porque tienen al \( 3 \) como m.c.d
\( 5,10,15 \) son todos adyacentes entre si, porque tienen al \( 5 \) como m.c.d
\( 7,14 \) son todos adyacentes entre si, porque tienen al \( 7 \) como m.c.d

Observa que \( 1,11,13 \) son vértices aislados.

Con eso concluye que hay cuatro componentes conexas y determina cuales son.

Además deduce que hay un camino que une todos los vértices excepto el \( 1,11,13 \) y por tanto el camino de máxima longitud une \( 12 \) vértices.

Saludos.