Autor Tema: Componentes conexas

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

22 Noviembre, 2019, 05:26 am
Leído 953 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre o encuentre un contraejemplo para la siguiente afirmacion. Un grafo conexo \( G \) tiene un vertice \( v \) tal que \( G-v \) tiene mas de una componente conexa si y solo si \( G^{*} \) tiene un vertice \( v^{*} \) tal que \( G^{*}-v^{*} \) tiene estrictamente mas componentes conexas que \( G^{*}. \)

Hola, no entiendo lo que hay que hacer... ???
"Haz de las Matemáticas tu pasión".

22 Noviembre, 2019, 08:52 am
Respuesta #1

Bobby Fischer

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 558
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
    • chess.com
Hola, yo supongo que un vértice no es una componente conexa. En tal caso, y suponiendo que G estrella sea G menos v, puedes considerar una línea quebrada con 5 vértices. El único vértice que puedes eliminar para que aparezca más de una componente conexa es el de en medio. Aparecen dos componentes conexas. Si la afirmación fuese cierta, debería haber un vértice de este grafo resultante tal que al quitarlo aparecen más componentes conexas que 2. Cualquier vértice que quites da sólo 1 componente conexa. Suponiendo que un vértice aislado sí es componente conexa, considera un grafo estrellado. El único vértice que puedes quitar para que aparezca más de una componente conexa es el de en medio. Se halla un contraejemplo de forma análoga, pues en el subgrafo resultante, cualquier vértice que retires da un subgrafo con menor número de vértices (componentes conexas) que aquel de donde proviene.

22 Noviembre, 2019, 12:25 pm
Respuesta #2

Luis Fuentes

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

Demuestre o encuentre un contraejemplo para la siguiente afirmacion. Un grafo conexo \( G \) tiene un vertice \( v \) tal que \( G-v \) tiene mas de una componente conexa si y solo si \( G^{*} \) tiene un vertice \( v^{*} \) tal que \( G^{*}-v^{*} \) tiene estrictamente mas componentes conexas que \( G^{*}. \)

Hola, no entiendo lo que hay que hacer... ???

Normalmente \( G^* \) se refiere al grafo dual de un grafo planar. Pero tu dirás con que significado lo estás manejando.

En ese caso el resultado sería igualmente falso. Considera el grafo (en negro y azul) y su dual. Saca tus conclusiones.



Saludos.