Matemática => Teoría de grafos => Mensaje iniciado por: Julio_fmat en 06 Diciembre, 2019, 00:30



Título: Cobertura de vértices \(\Leftrightarrow \) complementario conjunto independiente
Publicado por: Julio_fmat en 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?


Título: Re: Cobertura de vértices \(\Leftrightarrow \) complementario conjunto independiente
Publicado por: Luis Fuentes en 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.