10 Abril, 2020, 05:32 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Cobertura de vértices \(\Leftrightarrow \) complementario conjunto independiente  (Leído 137 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.110



Ver Perfil WWW
« : 06 Diciembre, 2019, 00:30 »

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

Hola, cómo podemos hacer este problema?
En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 09 Diciembre, 2019, 10:23 »

Hola

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

Hola, cómo podemos hacer este problema?

Si [texx]X[/texx] es una cobertura, entonces toda arista del grafo incide en algún vértice de [texx]X[/texx]. Por tanto no puede haber una arista uniendo dos vértices del complementario de [texx]X[/texx] 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 [texx]X[/texx]. Por tanto [texx]X[/texx] 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.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!