Autor Tema: Cobertura de vértices \(\Leftrightarrow \) complementario conjunto independiente

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

06 Diciembre, 2019, 04:30 am
Leído 845 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 \( X \) es una cobertura de vértices en un grafo \( G \) si y solo si \( V(G)\setminus X \) es un conjunto independiente. Deduzca que \( \beta(G)=n(G)-\alpha(G). \)

Hola, cómo podemos hacer este problema?
"Haz de las Matemáticas tu pasión".

09 Diciembre, 2019, 02:23 pm
Respuesta #1

Luis Fuentes

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

Demuestre que \( X \) es una cobertura de vértices en un grafo \( G \) si y solo si \( V(G)\setminus X \) es un conjunto independiente. Deduzca que \( \beta(G)=n(G)-\alpha(G). \)

Hola, cómo podemos hacer este problema?

Si \( X \) es una cobertura, entonces toda arista del grafo incide en algún vértice de \( X \). Por tanto no puede haber una arista uniendo dos vértices del complementario de \( X \) y así tal conjunto complementario es un conjunto independiente.

Recíprocamente si el complementario es independiente no puede haber una arista uniendo dos vértices de tal complementario y así toda arista necesariamente incide el un vértice de \( X \). Por tanto \( X \) es una cobertura.

Para la segunda parte usa lo anterior y la definición de conjunto maximal independiente y cobertura minimal.

Como siempre: si no te sale, concreta las dudas explicando que has intentado.

Saludos.