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



Título: Mostrar que X es un clique ssi X es independiente
Publicado por: Julio_fmat en 06 Diciembre, 2019, 00:19
Demuestre que [texx]X[/texx] es un clique en un grafo [texx]G[/texx] si y solo si [texx]X[/texx] es un conjunto independiente en [texx]\overline{G}[/texx]. Demuestre entonces que [texx]\omega(G)=\alpha(\overline{G}).[/texx]

Hola, sabemos que [texx]X[/texx] es un clique si [texx]\forall u,v\in X, \{u,v\}\in E[/texx].



Título: Re: Mostrar que X es un clique ssi X es independiente
Publicado por: Luis Fuentes en 09 Diciembre, 2019, 16:48
Hola

Demuestre que [texx]X[/texx] es un clique en un grafo [texx]G[/texx] si y solo si [texx]X[/texx] es un conjunto independiente en [texx]\overline{G}[/texx]. Demuestre entonces que [texx]\omega(G)=\alpha(\overline{G}).[/texx]

Hola, sabemos que [texx]X[/texx] es un clique si [texx]\forall u,v\in X, \{u,v\}\in E[/texx].

Simplemente, si  [texx]\{u,v\}\in E(G)[/texx] entonces [texx]\{u,v\}\not\in E(\overline{G})[/texx] y por tanto que todo par de vértices de [texx]X[/texx] este unido por una arista en [texx]G[/texx] equivale a que todo par de vértices en [texx]X[/texx] no está unido por ninguna arista en [texx]\bar G[/texx], es decir, equivale a que [texx]X[/texx] es un conjunto independiente en [texx]\bar G[/texx].

Saludos.