Autor Tema: Subgrafo bipartito recubridor

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

18 Noviembre, 2019, 05:36 am
Leído 832 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 que todo grafo tiene un subgrafo bipartito recubridor \( H \) que satisface \( d_H(v)\ge d_G(v)/2. \)
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 11:48 am
Respuesta #1

Luis Fuentes

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

Demuestre que todo grafo tiene un subgrafo bipartito recubridor \( H \) que satisface \( d_H(v)\ge d_G(v)/2. \)

Considera una partición cualquiera de los vértices de \( G \), \( V_1\cup V_2. \) y el correspondiente subgrafo bipartito que se obtiene quedándose con las aristas de \( G \) que unen vértices de \( V_1 \) con vértices de \( V_2 \).

Dado \( v\in V_1 \) si \( d_H(v)<d_G(v)/2 \) entonces cambiando el vértice \( v \) al conjunto \( V_2 \) se consigue un nuevo subgrafo bipartito \( H' \) tal que:

\( d_{H'}(v)=d_G(v)-d_H(v)>d_G(v)/2 \)

Ese grafo \( H' \) tiene estrictamente más aristas que el anterior (en concreto tiene \( d_{H'}(v)-d_H(v)=d_G(v)-2d_H(v) \) aristas más).

Por tanto dado un subgrafo bipartito recubridor que NO cumple la propiedad pedida siempre podemos construir otro subgrafo recubridor con estrictamente más aristas que el anterior. Como el número total de aristas está acotado, necesariamente terminamos por llegar a un subgrafo recubridor con la propiedad pedida.

Saludos.